Inorder, Preorder and Postorder Tree Traversal

Algorithm

Summary: In this tutorial, we will learn what is Inorder, Preorder and Postorder traversal method and how to implement these methods in C++ and Java.

A Tree which is a hierarchical (non-linear) data structure can be traversed in multiple ways unlike the linear data structure eg array, linked list, etc which can be traversed only in a linear fashion.

The basic two ways using which we can traverse a tree are:

  1. Depth First Traversal
    • Inorder
    • Preorder
    • Postorder
  2. Breadth First Traversal

In-order, pre-order, and post-order are three forms of depth-first search traversal method i.e. each method explores as far as possible along each branch before backtracking.

So let’s see how they differ form each other in context of depth-first traversal.

Inorder Traversal

  1. Left subtree.
  2. Root.
  3. Right subtree.

In the Inorder Traversal method, we first visit the left subtree then the root and after that to the right subtree of the tree.

Preorder Traversal

  1. Root.
  2. Left subtree.
  3. Right subtree.

In the Preorder traversal method, we start from the root, then we go the left subtree and finally to the right subtree.

Preorder Traversal

  1. Left subtree.
  2. Right subtree.
  3. Root.

In the Postorder tree traversal method, we first visit the left subtree and then the right subtree and finally the root.

Trick: Whichever method you use always remember that the left subtree always comes before the right subtree.

tree traversals

To implement these traversal methods we will use recursion because each part of the tree whether left or right is itself a tree (i.e. subtree).

In recursion, we treat each node as the root of the underlying subtree.

Here is the implementation of Pre-order, In-order, and Post-order traversal in C++ and Java.

Java

class Node{
  int value;
  Node left;
  Node right;
 
  //Constructor to initialize value to node
  Node(int value){
    this.value = value;
    left = right = null;
  }
 
  //Function to insert data i.e to form binary tree
  public void insert(int v){
 
    if(v < value){
      if(left == null){
        left = new Node(v);
      } else {
        left.insert(v);
      }
    } else {
      if(right == null){
        right = new Node(v);
      } else{
        right.insert(v);
      }
    }
  }
 
  //Function to perform Pre-Order Travesal
  public void preOrder(){
    //1. Root
    System.out.print(value+" ");
 
    //2. Left subtree
    if(left != null){
      left.preOrder();
    }
 
    //3. Right subtree
    if(right != null){
      right.preOrder();
    }
  }
 
  //Function to perform Post-Order Travesal
  public void postOrder(){
 
    //1. Left subtree
    if(left != null){
      left.postOrder();
    }
 
    //2. Right subtree 
    if(right != null){
      right.postOrder();
    }
 
    //3. Root
    System.out.print(value+" ");
  }
 
  //Function to perform In-Order Travesal
  public void inOrder(){
 
    //1. Left subtree
    if(left != null){
      left.inOrder();
    }
 
    //2. Root
    System.out.print(value+" ");
 
    //3. Right subtree 
    if(right != null){
      right.inOrder();
    }
  }
}
 
class Main {
  public static void main(String[] args) {
    Node root = new Node(25);
 
    root.insert(20);
    root.insert(31);
    root.insert(19);
    root.insert(23);
    root.insert(26);
    root.insert(36);
 
    System.out.print("\n Inorder: ");
    root.inOrder();
 
    System.out.print("\n Preorder: ");
    root.preOrder();
    
    System.out.print("\n Postorder: ");
    root.postOrder();
  }
}

C++

#include <iostream>
using namespace std;
 
//Class TreeNode represent each node
class TreeNode{
public:
    int data;
    TreeNode *leftNode {nullptr};
    TreeNode *rightNode {nullptr};
 
    TreeNode();
    TreeNode(int d);
    void insertData(int d);
    void inorderTraverse();
    void preorderTraverse();
    void postorderTraverse();
};
 
//Implementing TreeNode class prototypes function.
TreeNode::TreeNode(int d){
    data = d;
}
 
//Inserting node as a left child if it is smaller than the current node
//else it will be inserted as the right child
// Assuming no two numbers/nodes are same
void TreeNode::insertData(int d){
    if(d < data){
        if(leftNode == nullptr){
            leftNode= new TreeNode(d);
        } else {
            leftNode->insertData(d);
        }
    } else {
        if(rightNode == nullptr){
            rightNode = new TreeNode(d);
        } else {
            rightNode->insertData(d);
        }
    }
}
 
// Inorder traversal algorithm
void TreeNode::inorderTraverse(){
 
  //1.Left subtree
  if(leftNode != nullptr){
    leftNode->inorderTraverse();
  }
 
  //2. Root
  cout << data << " ";
 
  //3. Right subtree
  if(rightNode != nullptr){
    rightNode->inorderTraverse();
  }
}
 
// Preorder traversal algorithm
void TreeNode::preorderTraverse(){
 
  //1. Root
  cout << data << " ";
 
  //2.Left subtree
  if(leftNode != nullptr){
    leftNode->preorderTraverse();
  }
 
  //3. Right subtree
  if(rightNode != nullptr){
    rightNode->preorderTraverse();
  }
}
 
// Postorder Traversal Algorithm
void TreeNode::postorderTraverse(){
 
  //1.Left subtree
  if(leftNode != nullptr){
    leftNode->postorderTraverse();
  }
 
  //2. Right subtree
  if(rightNode != nullptr){
    rightNode->postorderTraverse();
  }
 
  //3. Root
  cout << data << " ";
}
 
int main()
{
  //Taking root node as 25
  TreeNode *root= new TreeNode(25);
 
  //inserting data into the binary tree
  root->insertData(20);
  root->insertData(31);
  root->insertData(19);
  root->insertData(23);
  root->insertData(26);
  root->insertData(36);
 
  //Calling inorder traversal function from root object
  cout << "\n Inorder: ";
  root->inorderTraverse();
 
  cout << "\n Preorder: ";
  root->preorderTraverse();
 
  cout << "\n Postorder: ";
  root->postorderTraverse();
 
  return 0;
}

Output:

In the above program, we have implemented the node as a class and linked other nodes using the insert method on the root.

By doing this we formed a Binary tree, then traversed it using the tree traversal methods.

In this tutorial, we learned what In-order, Pre-order and Post-order traversal are and how to implement them in C++ and Java programming languages.

One thought on “Inorder, Preorder and Postorder Tree Traversal”

Leave a Reply

Your email address will not be published. Required fields are marked *