Tree Traversal (In Order, Pre Order, Post Order)
Traversing a tree is the process of visiting every node in the tree. Since all nodes are connected via edges, traversal is always started from the root node.
It is not possible to randomly access a node in a tree.
Basic structure of a tree
Every tree consists of :
- A node carrying data or a value
- Two subtrees
struct node
{
int data;
struct node* left; // left child
struct node* right; // right child
}
Note : The struct node pointed to by left and right might have other left and right children and should be considered as sub-trees instead of sub-nodes.
A hierarchical data structure like a tree can be traversed in three ways :
- In-order Traversal
- Pre-order Traversal
- Post-order Traversal
In-order Traversal
In inorder traversal, the output will produce sorted key values in ascending order.
Steps
Until all nodes are traversed :
- Traverse left subtree.
- Then the root node.
- Traverse right subtree.
Note : Every node may represent a subtree itself.
Start from 3, then move to its left subtree 5. 5 is also traversed in-order.
The process goes on until all the nodes are visited.
The output of inorder traversal of this tree will be :
11 → 5 → 8 → 3 → 9 → 6 → 1
Code
void inorder(struct Node* node)
{
if (node != NULL)
{
inorder(node->left);
print(node->data);
inorder(node->right);
}
}
Preorder Traversal
Steps
- Visit root node.
- Traverse left subtree. (Visit all the nodes in the left subtree)
- Traverse right subtree. (Visit all the nodes in the right subtree)
Note : Every node may represent a subtree itself.
Start from 3, then first visit 3 itself and then move to its left subtree 5. 5 is also traversed pre-order.
The process goes on until all the nodes are visited.
The output of pre-order traversal of this tree will be :
3→ 5 → 11 → 8 → 6 → 9 → 1
Code
void preorder(struct Node* node)
{
if (node != NULL)
{
print(node->data);
preorder(node->left);
preorder(node->right);
}
}
Post-order Traversal
Steps
Until all nodes are traversed :
- Traverse left subtree.
- Traverse right subtree.
- Visit the root node.
Note : Every node may represent a subtree itself.
Start from 3,then traverse the left subtree 5. 5 is also traversed post-order.
The process goes on until all the nodes are visited.
The output of post-order traversal of this tree will be :
11 → 8 → 5 → 9 → 1 → 6 → 3
Code
void postorder(struct Node* node)
{
if (node != NULL)
{
postorder(node->left);
postorder(node->right);
print(node->data);
}
}
Implementation
This implementation is based on concepts used in Array Implementation Of Binary Trees