Binary Tree Traversal Algorithms

                                                                                                          B Trees
A Binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. "Root" node is used as reference to the to most parent in the tree.
Consider the following tree Root node of this tree will point to 7.

Now for Traversing binary tree there are three algorithms.

First is Preorder traversal: To traverse a binary tree in Preorder, the procedure is

(i)                  Visit the root,

(ii)                Traverse the left subtree, and

(iii)               Traverse the right subtree.

Therefore, the Preorder traversal of the above tree will outputs:
7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10
and the recursive algorithm is 

Second is Inorder traversal: To traverse a binary tree in Inorder, the procedure is

(i)                 Traverse the left subtree.

(ii)                Visit the root, and

(iii)               Traverse the right subtree.

Therefore, the Inorder traversal of the above tree will outputs:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10and the recursive algorithm is 

Third is Postorder traversal: To traverse a binary tree in Postorder, the procedure is

(i)        Traverse the left subtree,

(ii)               Traverse the right subtree,

(iii)               Visit the root

Therefore, the Inorder traversal of the above tree will outputs:

0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7
and the recursive algorithm is

 

-----------

Vinay Kumar Saini                                                                    

Assistant Professor (I.T Department)

Maharaja Agrasen Institute of Technology (MAIT)

Sector-22, Rohini, Delhi-110086, India
Email-Id : vinay.kr.saini@gmail.com
Connect with me

Visit My Blog: http://vinay-kumar-saini.blogspot.in/