Traversal in Binary Trees

http://install4install.com

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

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

 



Short URL: http://tinyit.cc/4e9e08
Author: Cusp2207 on May 7, 2014
Category: Computer Science, Data Structures
Tags:

Leave a Reply

Last articles