Binary Tree Traversals

 Tree Traversal refers to the process of visiting each node in a tree data structure exactly once

OR

Displaying (or) visiting order of nodes in a binary tree is called as Binary Tree Traversal.

 
Various tree traversal techniques are-

Depth First Traversal-

Following three traversal techniques fall under Depth First Traversal-

1. Preorder Traversal
2. Inorder Traversal
3. Postorder Traversal

 

Preorder Traversal-

 Algorithm-

1. Visit the root
2. Traverse the left sub tree i.e. call Preorder (left sub tree)
3. Traverse the right sub tree i.e. call Preorder (right sub tree)

 

Root → Left → Right

 Exmple

 Preorder Traversal : A B D E C FG

 

Inorder Traversal-

 Algorithm-

1. Traverse the left sub tree i.e. call Inorder (left sub tree)
2. Visit the root
3. Traverse the right sub tree i.e. call Inorder (right sub tree)

 

Left → Root → Right

 

 

Inorder Traversal :  D B E A F C G

Postorder Traversal-

 

Algorithm-

1. Traverse the left sub tree i.e. call Postorder (left sub tree)
2. Traverse the right sub tree i.e. call Postorder (right sub tree)
3. Visit the root

 

Left → Right → Root

 

 Postorder Traversal :  D E B F G C A

 

Breadth First Traversal-

• Breadth First Traversal of a tree prints all the nodes of a tree level by level.
• Breadth First Traversal is also called as Level Order Traversal.

 

Example

 

Level order traversal: A B C D E F G

 

 

PRACTICE PROBLEMS BASED ON TREE TRAVERSAL-

 

Problem-01:

 If the binary tree in figure is traversed in inorder, then the order in which the nodes will be visited is ____? 

 

Solution

The inorder traversal will be performed as-

 

G C B D A F E

 

Problem-02:

 Which of the following sequences denotes the postorder traversal sequence of the tree shown in figure?

 

 Solution

The Postorder traversal will be performed as-

 

G C D  B F E A