Binary Tree Traversing Techniques

 Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical way to traverse them, trees can be traversed in different ways. Following are the generally used ways for traversing trees.

Traversing a binary tree is the process of visiting each node in the tree exactly once, in a systematic way. There are four common ways to traverse a binary tree.

Depth First Traversals:

(a) Inorder Traversal
(b) Preorder Traversal
(c) Postorder Traversal

Breadth First or Level Order Traversal.

(1) Inorder Traversal

In case of Inorder Traversal, the root of each subtree is visited after its left and right subtree has been traversed but before the traverse of its right subtree begins. The steps for traversing a binary tee in Inorder are:

1.Traverse the left most sub tree in Inorder
2.Visit the root.
3.Traverse the right most sub tree in Inorder.

Note: Inorder traversal is also known as LNR traversal.

Algorithm for Inorder 

2) Preorder Traversal

In a preorder Traversal, each root node is visited first before its left and right sub trees are traversed. Preorder search is also known as backtracking. The steps in preorder traveling are:

1. Visit the root.
2. Visit the left subtree, using preorder.
3. Visit the right subtree, using preorder.

Note: Inorder traversal is also known as NLR traversal.

Algorithm for Preorder 

3) Postorder Traversal

In Postorder Traversal, each root is visited after its left and right subtrees have been traversed. The steps for traversing a binary tree in Postorder Traversal are:

1. Visit the left subtree, using postorder.
2. Visit the right subtree, using postorder
3. Visit the root.

4) Level Order Traversal

In a Level Order Traversal, the nodes are visited level by level starting from the root and going from left to right. This Level Order Traversal requires Queue data structure. So, it is not possible to develop recursive procedures to traverse the binary tree in level order. This is nothing but a breadth first search technique.


For example consider the following simple tree

For the given tree the following are the paths

Inorder (Left, Root, Right): 4 2 5 1 3
Preorder (Root, Left, Right): 1 2 4 5 3
Postorder (Left, Right, Root): 4 5 2 3 1
Level Order Traversal: 1 2 3 4 5