Tree Traversal Techniques

Tree Traversal

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

-> Different tree traversal techniques are:-

1. Depth first Traversal - 

there are 3 techniques in depth first traversal -

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


1. Preorder Traversal:- 

Algorithm - 

1. visit the root.
2. traverse the left sub tree.
3. traverse the right sub tree.

                          Root -> left -> right


-> Preorder Traversal Shortcut

-> Traverse the entire tree starting from the root node keeping yourself to the left.

Applications:-

1. Preorder traversal is used to get prefix expression of an expression tree.
2. Preorder traversal is used to create a copy of the tree.
3. Preorder traversal is used to get prefix expression of an expression tree.

2. 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 Shortcut

-> Keep a plane mirror horizontally at the bottom of the tree and take the projection of all the nodes.

Application-

1. Inorder traversal is used to get infix expression of an expression tree.



3. 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 Shortcut

-> Pluck all the leftmost leaf nodes one by one.

Applications-

1. Postorder traversal is used to delete the tree.
2. This is because it deletes the children first and then it deletes the parent.
3. Postorder traversal is used to get postfix expression of an expression tree.




2. 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.

Application-

1. Level order traversal is used to print the data in the same order as stored in the array representation of a complete binary tree.