How to Solve: Binary Tree Inorder/Preorder/Postorder Traversal (Recursive & Iterative) – Complete Guide

How to Solve: Binary Tree Inorder/Preorder/Postorder Traversal (Recursive & Iterative) – Complete Guide

? Introduction

"This pattern appears in 1 out of every 3 FAANG onsite interviews—master it, and you prove you can handle recursion, stacks, and tree traversals with surgical precision."

? WHAT YOU NEED TO KNOW FIRST

Before diving in, ensure you understand: 1. Binary Tree Structure – Nodes, left/right children, root, leaf nodes. 2. Recursion – Call stack, base cases, recursive cases. 3. Stack Data Structure – LIFO (Last-In-First-Out) for iterative traversals.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

Follow this exact order for every traversal problem:

1. Identify the Traversal Type

• Inorder → Left → Root → Right
• Preorder → Root → Left → Right
• Postorder → Left → Right → Root

2. Choose Recursive or Iterative

• Recursive → Cleaner code, but risk of stack overflow for deep trees.
• Iterative → More control, no recursion limit, but more complex.

3. Write the Recursive Solution (If Allowed)

• Base Case: if not node: return
• Recursive Case: Call traversal on left/right children in the correct order.
• Visit Node: Process the node (print, append to list, etc.).

4. Write the Iterative Solution (If Required)

• Inorder:
• Use a stack.
• Push all left nodes until None.
• Pop, visit, then move to right.
• Preorder:
• Use a stack.
• Push right first, then left (so left is processed first).
• Postorder:
• Option 1: Two stacks (reverse preorder).
• Option 2: Single stack + prev pointer to track last visited node.

5. Edge Cases & Validation

• Empty tree (root = None).
• Single-node tree.
• Skewed tree (left or right heavy).

6. Time & Space Complexity

• Time: O(n) (visit every node once).
• Space:
• Recursive: O(h) (call stack, where h = tree height).
• Iterative: O(h) (stack space).

? WORKED EXAMPLES

Example 1 – Basic: Recursive Inorder Traversal

Problem: Given a binary tree, return its inorder traversal (left-root-right).

Thought Process

1. Identify Traversal Type: Inorder → Left → Root → Right.
2. Choose Recursive: Simple and clean.
3. Base Case: If node is None, return.
4. Recursive Case: Traverse left, visit node, traverse right.

Code (Python)

def inorderTraversal(root):

    res = []

    def traverse(node):

        if not node:

            return

        traverse(node.left)   # Left

        res.append(node.val)  # Root

        traverse(node.right)  # Right

    traverse(root)

    return res

Complexity

• Time: O(n) (visit every node once).
• Space: O(h) (recursion stack, where h = tree height).

Why This Works

• Recursion naturally follows the call stack, which mimics the traversal order.
• Base case ensures we stop at None nodes.

Example 2 – Medium: Iterative Preorder Traversal

Problem: Given a binary tree, return its preorder traversal (root-left-right) iteratively.

Thought Process

1. Identify Traversal Type: Preorder → Root → Left → Right.
2. Choose Iterative: No recursion allowed.
3. Use a Stack:
4. Push root first.
5. While stack is not empty:
   • Pop node, visit it.
   • Push right child first, then left (so left is processed first).

Code (Python)

def preorderTraversal(root):

    if not root:

        return []

    stack, res = [root], []

    while stack:

        node = stack.pop()

        res.append(node.val)  # Visit root

        if node.right:        # Push right first

            stack.append(node.right)

        if node.left:         # Then left (processed first)

            stack.append(node.left)

    return res

Complexity

• Time: O(n) (visit every node once).
• Space: O(h) (stack space).

Why This Works

• Stack processes nodes in reverse order (LIFO).
• Pushing right first ensures left is processed next.

Example 3 – Hard/Follow-up: Iterative Postorder Traversal (Single Stack)

Problem: Given a binary tree, return its postorder traversal (left-right-root) iteratively using only one stack.

Thought Process

1. Identify Traversal Type: Postorder → Left → Right → Root.
2. Choose Iterative: No recursion, and only one stack allowed.
3. Trick: Use a prev pointer to track the last visited node.
4. If prev is the parent of the current node, we’re coming up from the left/right.
5. If prev is the left child, we need to process the right child.
6. If prev is the right child, we can process the root.

Code (Python)

def postorderTraversal(root):

    if not root:

        return []

    stack, res = [root], []

    prev = None

    while stack:

        node = stack[-1]  # Peek

        # If coming down from parent (no children processed yet)

        if not prev or prev.left == node or prev.right == node:

            if node.left:      # Go left

                stack.append(node.left)

            elif node.right:   # Go right

                stack.append(node.right)

        # If coming up from left child (right exists but not processed)

        elif node.left == prev and node.right:

            stack.append(node.right)

        # If coming up from right child (process root)

        else:

            res.append(node.val)

            stack.pop()

        prev = node

    return res

Complexity

• Time: O(n) (visit every node once).
• Space: O(h) (stack space).

Why This Works

• The prev pointer helps determine whether we’re moving down or up the tree.
• We only process the root after both children are visited.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. For any tree traversal problem, follow this checklist:

1. Identify the order: Inorder (left-root-right), Preorder (root-left-right), or Postorder (left-right-root).
2. Choose recursive or iterative:
3. Recursive is cleaner but risks stack overflow.
4. Iterative uses a stack and is safer for deep trees.
5. For recursive:
6. Base case: if not node: return.
7. Recursive case: Call left/right in the correct order.
8. For iterative:
9. Inorder: Push left nodes, pop, visit, then right.
10. Preorder: Push right first, then left (so left is processed first).
11. Postorder: Use a prev pointer to track last visited node.
12. Edge cases: Empty tree, single node, skewed tree.
13. Complexity: Always O(n) time, O(h) space.

Memorize the code templates, and you’ll crush any tree traversal question in under 10 minutes. Now go practice!

? Final Notes

• Practice: Implement all three traversals (recursive + iterative) on LeetCode (e.g., 94. Binary Tree Inorder Traversal).
• Follow-ups: Be ready for "O(1) space" (Morris Traversal) or "reverse the traversal" (e.g., reverse postorder for preorder).
• Whiteboard Tip: Draw the tree and trace the traversal order before coding.

You’ve got this! ?