Tree Traversal Postorder Left Right Root in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Postorder Traversal on a Simple Binary Tree

What is the output of the following Java code performing postorder traversal (Left, Right, Root) on the given binary tree?

DSA Java

class Node {
    int data;
    Node left, right;
    Node(int data) {
        this.data = data;
        left = right = null;
    }
}

public class Main {
    static void postorder(Node root) {
        if (root == null) return;
        postorder(root.left);
        postorder(root.right);
        System.out.print(root.data + " ");
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        postorder(root);
    }
}

A 1 2 3 4 5

B 4 5 2 3 1

C 2 4 5 3 1

D 4 2 5 3 1

💡 Hint

Remember postorder traversal visits left subtree, then right subtree, then the root node.

Postorder traversal visits nodes in Left, Right, Root order. For the tree: 1 / \ 2 3 / \ 4 5 The traversal order is 4 (left of 2), 5 (right of 2), 2 (root of left subtree), 3 (right subtree), 1 (root).

🧠 Conceptual

intermediate

Number of Nodes Visited Before Root in Postorder Traversal

In postorder traversal (Left, Right, Root) of a binary tree with 7 nodes, how many nodes are visited before the root node is processed?

A 6

B 7

C 3

D 0

💡 Hint

Postorder visits all children before the root.

Postorder traversal visits all nodes in left and right subtrees before visiting the root. So for 7 nodes, the root is visited last after the other 6 nodes.

🔧 Debug

advanced

Identify the Error in Postorder Traversal Code

What error will the following Java code produce when performing postorder traversal?

DSA Java

class Node {
    int data;
    Node left, right;
    Node(int data) {
        this.data = data;
        left = right = null;
    }
}

public class Main {
    static void postorder(Node root) {
        if (root == null) return;
        postorder(root.right);
        postorder(root.left);
        System.out.print(root.data + " ");
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        postorder(root);
    }
}

A NullPointerException

B No error, output: 2 3 1

C StackOverflowError due to infinite recursion

D No error, output: 3 2 1

💡 Hint

Check the order of recursive calls for left and right subtrees.

The code visits right subtree first, then left subtree, then root. This is a reversed postorder traversal (Right, Left, Root). It runs without error and outputs 3 2 1.

❓ Predict Output

advanced

Output of Postorder Traversal on Unbalanced Tree

What is the output of the postorder traversal on this unbalanced binary tree?

DSA Java

class Node {
    int data;
    Node left, right;
    Node(int data) {
        this.data = data;
        left = right = null;
    }
}

public class Main {
    static void postorder(Node root) {
        if (root == null) return;
        postorder(root.left);
        postorder(root.right);
        System.out.print(root.data + " ");
    }

    public static void main(String[] args) {
        Node root = new Node(10);
        root.right = new Node(20);
        root.right.right = new Node(30);
        postorder(root);
    }
}

A 30 20 10

B 10 20 30

C 20 30 10

D 30 10 20

💡 Hint

Postorder visits left, then right, then root. Left subtree is empty here.

The tree structure is: 10 \ 20 \ 30 Postorder visits left (none), right subtree (30), then root (20), then root (10). So output is 30 20 10.

🚀 Application

expert

Number of Recursive Calls in Postorder Traversal

Given a full binary tree with 15 nodes, how many total recursive calls to the postorder function are made during a complete postorder traversal?

A 15

B 30

C 31

D 29

💡 Hint

Each node causes calls for itself and its null children.

Each node calls postorder on left and right child plus itself. For a full binary tree with 15 nodes, there are 16 null children (leaves have null children). Total calls = nodes + null calls = 15 + 16 = 31.

Practice

1. What is the correct order of nodes visited in a postorder tree traversal?

easy

A. Root node, Left subtree, Right subtree

B. Left subtree, Right subtree, Root node

C. Root node, Right subtree, Left subtree

D. Right subtree, Left subtree, Root node

Solution

1. Step 1: Understand postorder traversal definition

   Postorder traversal visits nodes in the order: left subtree first, then right subtree, and finally the root node.

2. Step 2: Match the order with options

   Left subtree, Right subtree, Root node matches the order Left, Right, Root exactly.

3. Final Answer:

   Left subtree, Right subtree, Root node -> Option B

4. Quick Check:

   Postorder = Left, Right, Root [OK]

Hint: Remember: postorder ends with root after children [OK]

Common Mistakes:

• Confusing postorder with preorder or inorder
• Visiting root before children
• Swapping left and right subtree order

2. Which of the following Java method signatures correctly represents a recursive postorder traversal of a binary tree node named root?

easy

A. void postorder(Node root) { postorder(root.left); postorder(root.right); visit(root); }

B. void postorder(Node root) { visit(root); postorder(root.left); postorder(root.right); }

C. void postorder(Node root) { postorder(root.right); postorder(root.left); visit(root); }

D. void postorder(Node root) { visit(root.left); visit(root.right); visit(root); }

Solution

1. Step 1: Recall postorder traversal steps

   Postorder visits left subtree, then right subtree, then root node (visit).

2. Step 2: Check each method's order

   void postorder(Node root) { postorder(root.left); postorder(root.right); visit(root); } calls postorder on left, then right, then visits root, matching postorder correctly.

3. Final Answer:

   void postorder(Node root) { postorder(root.left); postorder(root.right); visit(root); } -> Option A

4. Quick Check:

   Left, Right, Root method order = void postorder(Node root) { postorder(root.left); postorder(root.right); visit(root); } [OK]

Hint: Postorder calls left, right, then visit root [OK]

Common Mistakes:

• Visiting root before children
• Swapping left and right recursive calls
• Using visit instead of recursive call for children

3. Given the binary tree below:

    1
   / \
  2   3
 / \
4   5

What is the output of the postorder traversal?

medium

A. [1, 2, 3, 4, 5]

B. [2, 4, 5, 3, 1]

C. [4, 5, 2, 3, 1]

D. [4, 2, 5, 3, 1]

Solution

1. Step 1: Traverse left subtree of root (1)

   Left subtree rooted at 2: postorder visits 4 (left), 5 (right), then 2 (root) -> [4, 5, 2]

2. Step 2: Traverse right subtree and root

   Right subtree is 3 (leaf), so visit 3, then visit root 1 -> [3, 1]

3. Step 3: Combine all parts

   Full postorder: left subtree [4,5,2], right subtree [3], root [1] -> [4, 5, 2, 3, 1]

4. Final Answer:

   [4, 5, 2, 3, 1] -> Option C

5. Quick Check:

   Postorder = Left, Right, Root = [4,5,2,3,1] [OK]

Hint: Visit left subtree fully, then right, then root last [OK]

Common Mistakes:

• Visiting root before children
• Mixing up left and right subtree order
• Outputting preorder or inorder instead

4. Consider this Java method for postorder traversal:

void postorder(Node root) {
  if (root == null) return;
  postorder(root.right);
  postorder(root.left);
  visit(root);
}

What is the main problem with this code?

medium

A. It visits right subtree before left subtree, reversing order

B. It causes infinite recursion

C. It visits the root before children

D. It does not check for null root

Solution

1. Step 1: Analyze traversal order in code

   The code calls postorder on right subtree first, then left subtree, then visits root.

2. Step 2: Compare with correct postorder order

   Correct postorder is left, right, root. This code reverses left and right subtree order.

3. Final Answer:

   It visits right subtree before left subtree, reversing order -> Option A

4. Quick Check:

   Left before right needed, code does right before left [OK]

Hint: Left subtree must be visited before right in postorder [OK]

Common Mistakes:

• Swapping left and right subtree calls
• Ignoring null check (though present here)
• Visiting root before children

5. You want to collect all node values of a binary tree in postorder traversal into a list. Which of the following Java code snippets correctly implements this?

hard

A. void postorder(Node root, List<Integer> result) { if(root==null) return; postorder(root.left, result); result.add(root.val); postorder(root.right, result); }

B. void postorder(Node root, List<Integer> result) { if(root==null) return; result.add(root.val); postorder(root.left, result); postorder(root.right, result); }

C. void postorder(Node root, List<Integer> result) { if(root==null) return; postorder(root.right, result); postorder(root.left, result); result.add(root.val); }

D. void postorder(Node root, List<Integer> result) { if(root==null) return; postorder(root.left, result); postorder(root.right, result); result.add(root.val); }

Solution

1. Step 1: Understand postorder traversal with list collection

   Postorder visits left subtree, then right subtree, then adds root value to list.

2. Step 2: Check each code snippet's order

   void postorder(Node root, List<Integer> result) { if(root==null) return; postorder(root.left, result); postorder(root.right, result); result.add(root.val); } calls postorder on left, then right, then adds root value last, matching postorder correctly.

3. Final Answer:

   void postorder(Node root, List<Integer> result) { if(root==null) return; postorder(root.left, result); postorder(root.right, result); result.add(root.val); } -> Option D

4. Quick Check:

   Left, Right, Root with result.add last = void postorder(Node root, List<Integer> result) { if(root==null) return; postorder(root.left, result); postorder(root.right, result); result.add(root.val); } [OK]

Hint: Add root value after left and right recursive calls [OK]

Common Mistakes:

• Adding root value before children
• Swapping left and right subtree calls
• Forgetting null check before recursion