Algorithm: Traverse binary tree

3,411 0
Summary

Binary tree traversal involves three fundamental methods: Pre-Order, In-Order, and Post-Order. Each method defines a distinct sequence for visiting nodes, specifically Root-Left-Right for Pre-Order, Left-Root-Right for In-Order, and Left-Right-Root for Post-Order. Applying these algorithms to a given tree results in unique node sequences, as demonstrated by an example tree. Developers commonly implement these traversals using both recursive and non-recursive approaches to process tree structures efficiently.

Preface

There are three ways to traverse a binary tree based on the traversing order.

  • Pre-Order: Root - Left - Right
  • In-Order: Left - Root - Right
  • Post-Order: Left - Right - Root

Take below binary tree as example

The node to be traversed in different order would be

  • Pre-Order: A - B - C - D - E - F
  • In-Order: C - B - D - A - E - F
  • Post-Order: C - D - B - F - E - A

Below are the implementations of different orders for traversing the binary tree.

Pre-Order Traversing

Recursive implementation

Non-recursive implementation

In-Order traversing

Recursive implementation

Non-recursive implementation

Post-Order traversing

Recursive implementation

Reference: https://mp.weixin.qq.com/s/U7nZYrndMx2jdQf6dAxuww

ALGORITHM BINARY TREE

  RELATED

  COMMENTS

0

No comment for this article.