Binary Tree Traversal: Preorder, Inorder, Postorder - data structures tutorial

Prerequisites:  Pls refer to my post on What are trees and Binary search tree impleemtation before reading about Binary Tree Traversal: Preorder, Inorder, Postorder - data structures tutorial.

What does it mean by tree traversal? When would you require traversing trees and what are the different ways of traversing it? These are some common questions that many of you must have. Today,I'm gonna give you an A-Z guide on Binary Tree Traversal in Data Structures. So, let's start:

The meaning of tree traversal is to visit every node of the tree. Tree traversal is a very important concept that will help you guys in solving day to day problems based on trees like finding sum of all values of a tree, finding largest and smallest value of a tree and a lot more.

Tree is not a linear data structure that's why it can be traversed in different ways. Most commonly used ways of traversing a tree are:

• Inorder Traversal
• Preorder Traversal
• Postorder Traversal

Inorder traversal

In this traversal technique, we first traverse the left sub-tree then root and then the right sub-tree. Let's take an example to understand it more clearly:

1. First, the left subtree of node A will be taken.
2. In the left subtree, B is having another left subtree which has node D so it be taken.
3. D does not have any left subtree so it will be printed. 
4. Then root of D will be printed which is B.
5. Then right sub-tree of B will be printed which is E because further E does not have any left or right sub-tree.
6. Now, we are done with the left sub-tree of A, so we will print A also and we will move to right sub-tree.
7. In the right subtree we have C which has a left sub-tree containing F so it will be taken into account.
8. F does not have any left sub-tree so F will be printed.
9. Then root of F or C will be printed.
10. Then right sub-tree of C or G will be printed because further G does not have any left or right sub-tree..

In-order traversal of the tree is D->B->E->A->F->C->G


Pre-order Traversal

In this traversal technique, the root node is visited first, then left sub-tree and then right sun-tree. Let's take an example:

1. First we will print A.
2. Then we will visit left subtree of A.
3. The left subtree has B as root which itself has another left subtree so we will print B.
4. Now we ,will visit left subtree of B which has D only.
5. Since, D does not have any sub-trees thus we will print D .
6. Now we will move to right subtree of B which has E only.
7. Since E does not have any subtrees that's why we will now print E.
8. Now we are done with left sub-tree of A so we will move to right sub-tree of A.
9. It has C as root so C will be printed.
10. C has left subtree so we will move to left subtree of C which has F only.
11. Since, F does not have any subtrees that's why we will print F.
12. Now,we will visit right subtree of  C which has G only.
13. Since, G does not have any subtree so we will print G.

Pre-order traversal of tree is A->B->D->E->C->F->G 


Post-order Traversal

In this traversal technique, first we visit left sub-tree then right sub-tree and then the root. Let's take an example:

1. We will first visit left subtree of A.
2. In left subtree of A we have B as root which itself has a left and right subtree.
3. So, we will move to Left subtree of B which has D only.
4. Since D does not have any subtree so we will print D.
5. Now we will move to right subtree of B which has E only.
6. Since E does not have any subtree so we will print E itself.
7. Now we have printed left and right of B so we B will be printed now.
8. Now, we will move to right subtree of A which has C as root node which itself has a left and right subtree.
9. So, we will visit left subtree of C which has F only.
10. Since F does not have any subtree so we will print F.
11. Next,we will move to right subtree of C which has G only.
12. Since, G has no subtrees so we will print G.
13. Now we have printed left and right subtree of C so we will print C .
14. Now we have printed left and right subtree of  A so we will print A .

Post-order traversal of  tree is D->E->B->F->G->C->A 


Implementation of Preorder,Postorder,Inorder traversal in c++

NOTE: It is a humble request that you read about trees and its implementation first and then read the code below.

Links:

• What are trees in data structures.
• Binary search tree implementation.

Preorder(root)
{
   if(root==NULL)
      return ;
   cout<<root->data;
   Preorder(root->left);
   Preorder(root->right);
}

// We have passed root node as parameter because we will start traversal from root of the tree.
//  If root is NULL then we will simply terminate as shown in the if condition above.
//  Else we will first print the value of root and then move to left sub tree of that root by calling Preorder(root->left) recursively.
//  Now, we are in the left subtree.
//  Again we will check if root is Null or not.
//  If It is not Null, then we will print root of left subtree and then we will move to the left subtree of that root also.
// Now we are in the left left subtree .
// Assuming that no further tree exist now , we will return out of this recursive function because this time root==NULL.
// Now we are in the left subtree again .
// This time we will go to the right subtree of the left subtree and the process continues if right subtree also has left or right subtree.

#include<iostream> using namespace std; struct bstnode { int data; bstnode* left; bstnode* right; }; void preorder(bstnode* root) { if(root==NULL) return; cout<<root->data<<" "; preorder(root->left); preorder(root->right); } void inorder(bstnode* root) { if(root==NULL) return ; inorder(root->left); cout<<root->data<<" "; inorder(root->right); } void postorder(bstnode* root) { if(root==NULL) return ; postorder(root->left); postorder(root->right); cout<<root->data<<" "; } bstnode* getnewnode(int data) { bstnode* newnode=new bstnode(); newnode->data=data; newnode->left=NULL; newnode->right=NULL; return newnode; } bstnode* insert(bstnode* root,int data) { if(root==NULL) { root=getnewnode(data); } else if(root->data>=data) { root->left=insert(root->left,data); } else { root->right=insert(root->right,data); } return root; } bool searchnode(bstnode* root,int data) { if(root==NULL) return false; else if(root->data==data) return true; else if(data<=root->data) return searchnode(root->left,data); else return searchnode(root->right,data); } int main() { bstnode* root=NULL; root=insert(root,15); root=insert(root,10); root=insert(root,20); root=insert(root,25); root=insert(root,8); root=insert(root,12); cout<<"tree in the memory is as follow:"<<endl; cout<<" 15 "<<endl; cout<<" / \\ "<<endl; cout<<" 10 20 "<<endl; cout<<" / \\ \\ "<<endl; cout<<" 8 12 25 "<<endl; cout<<endl; cout<<"preorder traversal of tree is: "; preorder(root); cout<<endl; cout<<"inorder traversal of tree is: "; inorder(root); cout<<endl; cout<<"postorder traversal of tree is: "; postorder(root); cout<<endl; return 0; }

OUTPUT:

So, this was all about Binary Tree Traversal: Preorder, Inorder, Postorder - data structures tutorial. In the next post we will learn how to find height of a tree.