Facebook

Traversal in Binary Trees

Traversal means to move across/visit each and every node in the tree.There are three techniques to traverse a Binary Tree :

  • Preorder
  • Inorder
  • Postorder

Preorder traversal

In preorder traversal,firstly  the root is traversed then left subtree and in the last right subtree(Fig 1).

Fig 1 : Pre-order Traversal
Fig 1 : Technique of Pre-Order Traversal

Example

Consider the following binary tree(Fig 2) :

preorder
Fig 2 : Pre-Order Traversal
Screen Shot 2014-05-06 at 6.05.59 PM
Fig 3 : Traversal of nodes

 

Root is traversed in the beginning so 10 is visited at the first.After this left sub-tree is traversed. (Fig 3).  In the left subtree 22 is the root of 44 and 25,so 22 is visited after 10 followed by left child i.e.44.25 is the right child and  is the root node of 17 and 88.44 is followed by 25 then 17 and 88.After visiting left sub-tree traversal of right subtree is done.13 is visited and followed by left child i.e.46.

Inorder Traversal

In In-order traversal,left subtree is traversed in the  beginning  followed by  root  which is further followed by  right sub-tree(Fig 4).

Screen Shot 2014-05-06 at 4.28.13 PM
Fig 4 : Technique of In-order traversal

 

Example

Consider the following binary tree(Fig 5) :

inorder
Fig 5 : In-Order Traversal

 

Fig 6 : Traversal in In-Order
Fig 6 : Traversal of nodes

 

Post Order Traversal

In post-order traversal left subtree is traversed first followed by right subtree and further followed by root.

Screen Shot 2014-05-06 at 4.40.19 PM
Fig 7 : Technique of Post-Order traversal

 

Consider the following binary tree(Fig 5) :

postorder
Fig 8 : Post-order Traversal
Fig 9 : Post-Order Traversal
Fig 9 : Post-Order Traversal

 

Rate this post

Comments

So empty here ... leave a comment!

Leave a Reply

Your email address will not be published. Required fields are marked *

Sidebar