Binary Tree Traversal: Preorder, Inorder and Postorder Traversal
Tree is the important data structure. It has parent and children relationship at various level. The binary tree is tree data structure which has at most two children for every node. Here left and right children nodes are distinct. Unlike to other data structure such as an array, stack, queue, linked list; there are are many ways to traverse the elements of the binary tree. In this post, we see various types of binary tree traversal with its algorithm.
There are 3 standard types of depth search binary tree traversal and one breath search binary tree traversal
Depth Search Level order binary tree traversal
- Preorder binary tree traversal
- Inorder binary tree traversal
- Postorder binary tree traversal
Breath Search Level order binary tree traversal
We will see BFS traversal in another article.
Preorder Binary Tree Traversal
The First node will be visited then it will traverse to left subtree and then right subtree.
Algorithm Preorder(tree) Visit root node of the tree call preorder(left subtree) //recursion call call preorder(right subtree) //recursion call
Example: Preorder traversal of above tree is 4 1 7 3 5 6.
Use of preorder traversal:
Preorder traversal can be used to find out polish notation of the expression. Polish notation is useful to evaluate the expression effectively.
Inorder Binary Tree Traversal
The left subtree will be traversed first, then root node will be visited. After that, it will call to right subtree.
Algorithm Inorder(tree) call inorder(left subtree) //recursion call Visit root node of the tree call inorder(right subtree) // recursion call
Example: If we find the inorder traversal of above tree, it will be 7 1 3 4 5 6.
Use of inorder traversal:
If we apply inorder traversal on binary search tree it will give numbers in ascending order. So inorder traversal is used to find the numbers in increasing order for binary search tree.
Postorder Binary Tree Traversal
The left subtree and then right subtree will be traversed first. After that root node will be visited.
Algorithm Postorder(tree) call postorder(left subtree) // recursion call call postorder(right subtree) // recursion call Visit root node of the tree
Example: Postorder traversal of above tree is 7 3 1 6 5 4.
Use of postorder traversal:
It is used to find out postfix expression. It is also useful for deleting nodes in linked list. As elements at the bottom get deleted first, the structure of the tree after deletion of the bottom node will get preserved.
Preorder, inorder and postorder traversal are the depth first search traversal. We can traverse tree using breath first search traversal, that we will see in next article.