Tree traversal techniques: Inorder, Preorder and Postorder

Trees are widely used data structure in Computer Science.

A tree is a collection of nodes connected by edges, where each node has a parent node and zero or more child nodes.

The top-most node in a tree is called the root node, and the nodes with no children are called leaf nodes.

There are various techniques used to traverse a tree, three of the most common tree traversal techniques are Inorder, Preorder, and Postorder.

Consider we have below binary tree:

Binary tree

1. Inorder traversal (left, root, right)

In an Inorder traversal, we first visit the left child of the node, then the node itself, and then the right child of the node.

Inorder traversal of Binary Search Tree (BST) will be sorted in ascending order.

Inorder traversal of above tree is 12, 8, 9, 2, 14, 11, 29, 5, 4, 13, 3, 20, 7, 25, 30

2. Preorder traversal (root, left, right)

In an Preorder traversal, we first visit the node, then the left child of the node, and then the right child of the node

Preorder traversal of Binary Search Tree (BST) will be sorted in ascending order.

Preorder traversal of above tree is 4, 2, 8, 12, 9, 11, 14, 5, 29, 3, 13, 7, 20, 25, 30

3. Postorder traversal (left, right, root)

In an Postorder traversal, we first visit the left child of the node, then the right child of the node, and then the node itself.

This tree traversal technique is useful for deleting a tree, as it visits the child nodes before the parent node.

Postorder traversal of above tree is 12, 9, 8, 14, 29, 5, 11, 2, 13, 20, 30, 25, 7, 3, 4

You can refer below simple C++ code for tree traversals:

#include<iostream>
#include<vector>
#include<bits/stdc++.h>
using namespace std;

map<int,pair<int,int>> nodes;

void inOrder(int root)
{
  if(root==-1)
    return;
  inOrder(nodes[root].first);  // traverse left subtree
  cout<<root<<" ,";            // print current root node
  inOrder(nodes[root].second); // traverse right subtree
}

void preOrder(int root)
{
  if(root==-1)
    return;     
  cout<<root<<" ,";             // print current root node
  preOrder(nodes[root].first);  // traverse left subtree
  preOrder(nodes[root].second); // traverse right subtree
}

void postOrder(int root)
{
  if(root==-1)
    return;                      
  postOrder(nodes[root].first);  // traverse left subtree
  postOrder(nodes[root].second); // traverse right subtree
  cout<<root<<" ,";              // print current root node
}

int main()
{
  int n,i;
  cout<<"Enter total number of nodes: ";
  cin>>n;
  cout<<"\n";

  nodes.clear();
 
  int root, leftChild, rightChild;
  cout<<"Enter space seperated node, leftchild and rightchild for "<<n<<" nodes\n";
  for(i=0;i<n;i++) {
    cin>>root>>leftChild>>rightChild;
    nodes[root]={leftChild,rightChild}; 
  }
 
  cout<<"Enter root node of tree: ";
  cin>>root;
 
  cout<<"Inorder: ";
  inOrder(root);  // left,root,right
  cout<<"\n";
 
  cout<<"Preorder: ";  
  preOrder(root); // root,left,right
  cout<<"\n"; 
 
  cout<<"Postorder: ";
  postOrder(root); // left,right,root
}

Output will be below when you execute above code:

Enter total number of nodes: 15
Enter space seperated node, leftchild and rightchild for 15 nodes
4 2 3
2 8 11
3 13 7
8 12 9
11 14 5
13 -1 -1
7 20 25
12 -1 -1
9 -1 -1
14 -1 -1
5 29 -1
20 -1 -1
25 -1 30
29 -1 -1
30 -1 -1
Enter root node of tree: 4
Inorder: 12 ,8 ,9 ,2 ,14 ,11 ,29 ,5 ,4 ,13 ,3 ,20 ,7 ,25 ,30
Preorder: 4 ,2 ,8 ,12 ,9 ,11 ,14 ,5 ,29 ,3 ,13 ,7 ,20 ,25 ,30
Postorder: 12 ,9 ,8 ,14 ,29 ,5 ,11 ,2 ,13 ,20 ,30 ,25 ,7 ,3 ,4

Thank you for reading, please follow if you like the article.

Subscribe to stay tuned for upcoming articles.