Traversal technique for binary tree

Traversing tree is another operation that can be perform on binary tree. Basically traversing is the process to visit all nodes of binary tree and may print their values too. We cannot access random node in tree, root node must be consider in first place. In traversing tree, three techniques can be used :

I. Preorder

II. Postorder

III. Inorder

Preorder traversal

In preorder traversal, we first visit the node then go to left subtree and then visit right subtree. The algorithm can be as follows :

Algorithm Preorder (t)

{

// t is binary tree

{

If t ≠ 0 then

Visit ( t );

Preorder ( t → lchild )

Preorder ( t → rchild )

}

}

For example consider the following binary tree

Starting from root node A, visit the root node itself and then focus on left subtree of A node and move towards the left subtree B. the process again goes on and moves towards the node D of left of B subtree. Then visit the next node C and again C node is also Pre-traverse.

             Thus the preorder traversal is ABDCEF.

 

Postorder traversal

In postorder traversal root node is visited last. First we visit left subtree then right subtree and then lastly node. The algorithm for postorder traversal is as follows :

Algorithm Postorder (t)

{

// t is binary tree

{

If t ≠ 0 then

Postorder (t → left )

Postorder (t → right) 

Visit ( t )

}

}

Consider the same example

We follow post order traversal starting from A, we first visit left subtree B. B again post traverse and visit node D. the process goes on untill all the nodes visited. Go to the right subtree C and again transverse tree in postorder. Thus the output of post order traversal technique is DBEFCA

Inorder traversal

In inorder traversal, first we visit the left subtree then visit node and then lastly visit right subtree. The algorithm for inorder traversal is as follows :

Algorithm Inorder ( t )

{

// t is binary tree

{ if t ≠ 0 then

Inorder ( t → left )

Visit ( t )

Inorder ( t → right )  

        } 

} 

For example consider the same above binary tree.

Here we start from A and follow the inorder traversal. Visit the left subtree B. B subtree is also traverse inorderly. The process goes on and visited all the nodes. The output of inorder traversal is DBAECF.