Three types of Traversal

Inorder Traversal

Let's look at the code first

// Java program for inorder traversals
import java.util.*;

// Structure of a Binary Tree Node
class Node {
    int data;
    Node left, right;

    Node(int v)
    {
        data = v;
        left = right = null;
    }
}

// Main class
class GFG {

    // Function to print inorder traversal
    public static void printInorder(Node node)
    {
        if (node == null)
            return;

        // First recur on left subtree
        printInorder(node.left);

        // Now deal with the node
        System.out.print(node.data + " ");

        // Then recur on right subtree
        printInorder(node.right);
    }

The traversal order is left child, then root, and finally right child. You can think of it as following a left-root-right sequence recursively upwards. In the context of a Binary Search Tree, inorder traversal will print the BST node values in ascending order on the console.

---

PostOrder Traversal

Let's look at the code first

class GFG {

    // Function to print inorder traversal
    public static void printInorder(Node node)
    {
        if (node == null)
            return;

        // First recur on left subtree
        printInorder(node.left);  

        // Then recur on right subtree
        printInorder(node.right);
      
      // Now deal with the node
        System.out.print(node.data + " ");
    }

It’s clear that the left child is processed first, then the right child, and finally the root. This gives us an important hint: ==the final element in a PostOrder Traversal is always the root of the entire tree==. We will use this insight in a later problem to reconstruct a tree given two types of traversals.

You can approach writing the PostOrder Traversal for a given tree as follows:

First, find the leftmost node of the entire tree (if there is no left child, look for the leftmost right child). Then traverse in left → right → root order. If you discover a right subtree or right node that hasn’t been traversed yet, you cannot go back up to the higher-level root.

Essentially, move downward: first look to the left, if there’s no left child then look to the right, and finally return to the root.

---

PreOrder Traversal

Let's look at the code first:

class GFG {

    // Function to print inorder traversal
    public static void printInorder(Node node)
    {
        if (node == null)
            return;

       // First deal with the node
        System.out.print(node.data + " ");
      
        // Then recur on left subtree
        printInorder(node.left);  

        // Then recur on right subtree
        printInorder(node.right);
      
    }

Unlike PostOrder Traversal, PreOrder Traversal prints the root node first, then the left subtree, and finally the right subtree. Clearly, the first printed element is the root of the entire tree. Using this concept, if a PreOrder sequence is given, you can quickly identify the root of the entire tree.

It also starts from the bottom, going first to the left, then to the right, and finally returning to the root node.

Some Examples

          (1)
         /   \
       (2)   (3)
      /  \   /  \
    (4)  (5)(6) (7)
   /  \       \
 (8)  (9)     (10)
              /
            (11)

Please write down the PreOrder / InOrder / PostOrder Traversal of this tree

Answer for this question

Click to See!

PreOrder: 1 → 2 → 4 → 8 → 9 → 5 → 3 → 6 → 10 → 11 → 7
PostOrder: 8 → 9 → 4 → 5 → 2 → 11 → 10 → 6 → 7 → 3 → 1
InOrder: 8 → 4 → 9 → 2 → 5 → 1 → 6 → 11 → 10 → 3 → 7

         (A)
       /     \
     (B)     (C)
    /  \       \
  (D)  (E)     (F)
      /       /   \
    (G)     (H)   (I)
               \
               (J)

Please write down the PreOrder / InOrder / PostOrder Traversal of this tree

The answer for this question

Click to See!

PreOrder: A → B → D → E → G → C → F → H → J → I
PostOrder:  D → G → E → B → J → H → I → F → C → A
InOrder: D → B → G → E → A → C → H → J → F → I