Home Data Structures Tree Traversal - Preorder, Inorder, Postorder

# Tree Traversal – Preorder, Inorder, Postorder

Traversing a Tree is done to visit each and every node of the tree. Since from a given node, there is more than one possible next node(more than one children) and we are performing sequential access/traversal (not parallel), some nodes must be deferred(stored for visiting later). This is often done via a stack (LIFO) data structure and using preorder or postorder or inorder methods.

Various Methods for Tree Traversal are

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

(root, left, right)

1. Visit the root element & print it.
2. Visit the left subtree by recursively calling preorder function.
3. Visit the right subtree by recursively calling preorder function.
###### Algorithm
```int preorder(tree){
if(tree == NULL)
return 0;

print(tree->data);
preorder(tree->left);
preorder(tree->right);

return 0;
}```

##### Inorder Traversal

(left, root, right)

1. Visit the left subtree by recursively calling inorder function.
2. Visit the root element & print it.
3. Visit the right subtree by recursively calling inorder function.
###### Algorithm
```int inorder(tree){
if(tree == NULL)
return 0;

print(tree->data);
inorder(tree->left);
inorder(tree->right);

return 0;
}```

##### Postorder Traversal

(left, right, root)

1. Visit the root element & print it.
2. Visit the left subtree by recursively calling preorder function.
3. Visit the right subtree by recursively calling preorder function.
###### Algorithm
```int postorder(tree){
if(tree == NULL)
return 0;

postorder(tree->left);
postorder(tree->right);
print(tree->data);

return 0;
}```
##### CPP code for Tree Traversal
```#include<bits/stdc++.h>
using namespace std;

class Node{

public:
Node *lchild,*rchild;
int data;

public:
Node(int x){
data = x;
lchild = NULL;
rchild = NULL;
}
};

int preorder(Node *tree){
if(tree == NULL)
return 1;

cout<<tree->data<<" ";
preorder(tree->lchild);
preorder(tree->rchild);

return 1;
}

int inorder(Node *tree){
if(tree == NULL)
return 1;

inorder(tree->lchild);
cout<<tree->data<<" ";
inorder(tree->rchild);

return 0;
}

int postorder(Node *tree){
if(tree == NULL)
return 1;

postorder(tree->lchild);
postorder(tree->rchild);
cout<<tree->data<<" ";

return 0;
}

int main(){

Node *tree = new Node(5);

tree->lchild = new Node(3);
tree->lchild->lchild = new Node(2);
tree->lchild->rchild = new Node(4);

tree->rchild = new Node(8);
tree->rchild->lchild = new Node(6);
tree->rchild->rchild = new Node(9);

cout<<"Preorder Traversal of the Tree is: ";
preorder(tree);
cout<<endl;

cout<<"Inorder Traversal of the Tree is: ";
inorder(tree);
cout<<endl;

cout<<"Postorder Traversal of the Tree is: ";
postorder(tree);
cout<<endl;

return 0;
}
```
```Input Tree:
5
/   \
3     8
/  \   /  \
2    4  6   9

Output:
Preorder Traversal of the Tree is: 5 3 2 4 8 6 9
Inorder Traversal of the Tree is: 2 3 4 5 6 8 9
Postorder Traversal of the Tree is: 2 4 3 6 9 8 5```

The time complexity all of the tree traversal algorithm(Preorder, Inorder, Postorder) is O(N), N is the number of nodes in the tree.