Tree Traversal Postorder Left Right Root in DSA Java

Mental Model

Visit the left child, then the right child, and finally the node itself. This order ensures children are processed before their parent.

Analogy: Imagine cleaning a family tree photo album: first you look at the pictures of the youngest family members on the left, then those on the right, and only after that you look at the picture of the parent.

    [A]
   /   \
 [B]   [C]
 / \     \
[D] [E]   [F]
↑ root

Dry Run Walkthrough

Input: Tree: A with children B (left), C (right); B has children D (left), E (right); C has right child F

Goal: Print nodes in postorder: left subtree, right subtree, then root

Step 1: Visit left subtree of A: move to B

    [A]
   /   \
 [B]↑  [C]
 / \     \
[D] [E]   [F]

Why: Start with left child to follow postorder left-right-root

Step 2: Visit left subtree of B: move to D

    [A]
   /   \
 [B]↑  [C]
 / \     \
[D]↑ [E]   [F]

Why: Go deeper left before processing B

Step 3: D has no children, print D

Output: D

Why: Leaf node reached, print it

Step 4: Visit right subtree of B: move to E

    [A]
   /   \
 [B]↑  [C]
 / \     \
[D]   [E]↑  [F]

Why: After left subtree, visit right subtree

Step 5: E has no children, print E

Output: D E

Why: Leaf node reached, print it

Step 6: Print B after its children

Output: D E B

Why: Postorder prints node after children

Step 7: Visit right subtree of A: move to C

    [A]
   /   \
 [B]    [C]↑
 / \     \
[D] [E]   [F]

Why: After left subtree, visit right subtree

Step 8: Visit left subtree of C: none, move to right subtree F

    [A]
   /   \
 [B]    [C]↑
 / \     \
[D] [E]   [F]↑

Why: No left child, go to right child

Step 9: F has no children, print F

Output: D E B F

Why: Leaf node reached, print it

Step 10: Print C after its children

Output: D E B F C

Why: Postorder prints node after children

Step 11: Print A after its children

Output: D E B F C A

Why: Root printed last in postorder

Result:

D E B F C A

Annotated Code

DSA Java

class TreeNode {
    char val;
    TreeNode left, right;
    TreeNode(char val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class PostorderTraversal {
    public static void postorder(TreeNode root) {
        if (root == null) return; // base case: empty node
        postorder(root.left); // traverse left subtree
        postorder(root.right); // traverse right subtree
        System.out.print(root.val + " "); // visit root last
    }

    public static void main(String[] args) {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');

        A.left = B; A.right = C;
        B.left = D; B.right = E;
        C.right = F;

        postorder(A);
        System.out.println();
    }
}

if (root == null) return; // base case: empty node

stop recursion when node is null

postorder(root.left); // traverse left subtree

go left first to process left subtree

postorder(root.right); // traverse right subtree

then go right to process right subtree

System.out.print(root.val + " "); // visit root last

print current node after children

Output

D E B F C A 

Complexity Analysis

Time: O(n) because each node is visited exactly once

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to iterative traversal with stack, recursive is simpler but uses call stack; iterative may use explicit stack but same O(n) time

Edge Cases

Empty tree (root is null)

No output, function returns immediately

DSA Java

if (root == null) return; // base case: empty node

Tree with single node

Prints the single node value

DSA Java

postorder(root.left); // traverse left subtree

Tree with only left or only right children

Traverses down the existing children and prints nodes in postorder

DSA Java

postorder(root.right); // traverse right subtree

When to Use This Pattern

When a problem asks to process children before their parent in a tree, use postorder traversal to visit left, right, then root nodes.

Common Mistakes

Mistake: Printing the root node before visiting children (preorder) instead of after
Fix: Move the print statement after recursive calls to left and right children

Mistake: Visiting right subtree before left subtree
Fix: Always call postorder on left child before right child to maintain left-right-root order

Summary

Postorder traversal visits left subtree, then right subtree, then the node itself.

Use it when you need to process children before their parent, such as deleting a tree or evaluating expressions.

The key insight is to print the node only after both its children have been processed.

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