Binary Tree Preorder Traversal - Recursive, Iterative & Morris Solutions

Introduction

Preorder traversal is one of the three fundamental depth-first tree traversal methods. The traversal order follows Root → Left → Right, meaning we:

1. Visit the current node first
2. Traverse the left subtree
3. Traverse the right subtree

Why Interviewers Love It

Preorder traversal is a common interview topic because:

• Tests understanding of recursion vs iteration trade-offs
• Foundation for many tree problems (serialization, cloning, path finding)
• Morris traversal tests advanced understanding of tree manipulation
• Simple enough to code quickly, complex enough to discuss trade-offs

When to Use Preorder

• Tree serialization/deserialization (LC 297)
• Creating a copy of the tree
• Getting prefix expression from expression tree
• Checking if tree is a subtree (LC 572)

Visual Intuition

        1
       / \
      2   3
     / \
    4   5

Preorder: 1 → 2 → 4 → 5 → 3
         (Root→Left→Right)

Visit order:
  Step 1: Visit 1 (root)
  Step 2: Go left, Visit 2
  Step 3: Go left, Visit 4
  Step 4: Backtrack, go right, Visit 5
  Step 5: Backtrack to 1, go right, Visit 3

Interactive Visualizer

Explore all three traversal methods interactively. Watch the algorithm step through the tree!

Method:RecursiveIterativeMorris

Speed:0.5x1x2x4x

Preorder (Root→Left→Right) - Iterative

Step 1 / 0INIT

Ready to start

Stack

Empty

Result

[]

Current

Visited

In Stack

⟲ Reset← Prev▶ PlayNext →

Solution 1: Recursive Approach

The recursive solution directly implements the definition: visit root, traverse left, traverse right.

Code Template

JavaPythonJavaScript

Loading...

How It Works

1. Base case: If node is null, return
2. Process root: Add current node’s value to result
3. Recurse left: Call preorder on left child
4. Recurse right: Call preorder on right child

The call stack implicitly handles the backtracking.

Solution 2: Iterative Approach (Stack)

The iterative approach has two implementation styles with the same core idea but different code organization.

Approach 1: Direct Pop and Visit (Concise)

This is the most intuitive approach. Key insight: push right child first, then left child, so left is processed first (LIFO).

JavaPythonJavaScript

Loading...

Step-by-Step Walkthrough:

Tree:     1
         / \
        2   3

Stack operations:
1. Push 1           Stack: [1]
2. Pop 1, visit     Result: [1], push 3, push 2 → Stack: [3, 2]
3. Pop 2, visit     Result: [1,2], Stack: [3]
4. Pop 3, visit     Result: [1,2,3], Stack: []

Final: [1, 2, 3]

Why Push Right First?

Stack is LIFO (Last-In-First-Out). We want to process left before right:

• Push right → it goes to bottom
• Push left → it goes to top
• Pop gets left first ✓

Approach 2: Using cur Pointer (Unified Template)

This approach uses a cur pointer to control traversal direction, maintaining a unified code structure with inorder and postorder traversals.

JavaPythonJavaScript

Loading...

Core Idea:

1. cur pointer: Tracks current traversal position
2. Go left: Visit each node immediately along the way (preorder characteristic)
3. Stack saves nodes: For later right subtree processing
4. Turn right: After going all the way left, move to right subtree

Why Use cur Pointer?

The benefit of using a cur pointer is forming a unified template for all three traversals:

• Preorder: Visit on entry (when going left)
• Inorder: Visit on exit (when popping from stack)
• Postorder: Visit after processing both children

This approach helps with memorization and understanding the essence of traversal algorithms.

Comparison of Two Approaches

Feature	Approach 1 (Direct Pop)	Approach 2 (cur Pointer)
Code Length	Shorter	Slightly longer
Understanding	Simple and intuitive	Requires understanding pointer movement
Consistency	Unique to preorder	Unified across three traversals
Best For	Only implementing preorder	Learning all three traversals

Recommendation: Use Approach 1 for cleaner code when only doing preorder; use Approach 2 to understand and memorize a unified template for all traversals.

Solution 3: Morris Traversal (O(1) Space)

Morris traversal achieves O(1) space by temporarily modifying the tree structure using threaded binary trees.

Key Idea

Instead of using a stack, we create temporary links (threads) from nodes back to their ancestors. This allows us to return to parent nodes without extra space.

Code Template

JavaPythonJavaScript

Loading...

Morris Preorder vs Inorder

The critical difference: when to visit the node.

• Preorder Morris: Visit node before creating thread and going left
• Inorder Morris: Visit node after returning via thread

Preorder timing:
1. No left child? → Visit, go right
2. Has left child, no thread? → Visit, create thread, go left
3. Has left child, thread exists? → Remove thread, go right

Key: Visit happens BEFORE going left!

Thread Visualization

Original:        After threading:
    1                  1
   / \                / \
  2   3              2   3
 / \                / \
4   5              4   5
                        \
                         → (thread to 2)

Unified Template: Code Structure for All Three Traversals

Using the cur pointer approach, we can maintain a unified code structure for preorder, inorder, and postorder traversals, changing only when we visit nodes.

Core Template

All three traversals follow the same framework:

TreeNode cur = root;
Deque<TreeNode> stack = new ArrayDeque<>();

while (cur != null || !stack.isEmpty()) {
    // Phase 1: Explore left
    while (cur != null) {
        // Preorder: visit node here ⭐
        stack.push(cur);
        cur = cur.left;
    }
    
    // Phase 2: Process stack top
    cur = stack.pop();
    // Inorder: visit node here ⭐
    
    // Phase 3: Move to right subtree
    cur = cur.right;
}

Comparing All Three Traversals

Preorder Traversal (Root-Left-Right)

while (cur != null || !stack.isEmpty()) {
    while (cur != null) {
        result.add(cur.val);  // ⭐ Visit on entry
        stack.push(cur);
        cur = cur.left;
    }
    cur = stack.pop();
    cur = cur.right;
}

Inorder Traversal (Left-Root-Right)

while (cur != null || !stack.isEmpty()) {
    while (cur != null) {
        stack.push(cur);
        cur = cur.left;
    }
    cur = stack.pop();
    result.add(cur.val);     // ⭐ Visit on exit
    cur = cur.right;
}

Postorder Traversal (Left-Right-Root)

TreeNode prev = null;
while (cur != null || !stack.isEmpty()) {
    while (cur != null) {
        stack.push(cur);
        cur = cur.left;
    }
    cur = stack.peek();
    
    if (cur.right == null || cur.right == prev) {
        result.add(cur.val);  // ⭐ Visit after both children
        stack.pop();
        prev = cur;
        cur = null;
    } else {
        cur = cur.right;
    }
}

Unified Template Comparison Table

Feature	Preorder	Inorder	Postorder
Visit Timing	Going left	Popping from stack	After both children
Initialization	cur = root	cur = root	cur = root; prev = null
Left Exploration	push + visit + left	push + left	push + left
Stack Operation	pop	pop	peek
Right Processing	Direct move	Direct move	Conditional move
Extra Variables	None	None	prev (marks visited)

Memory Tricks

Preorder = Visit Early: Visit when entering node, then continue left

• Like greeting a new friend first, then getting to know them deeper

Inorder = Visit Middle: After processing left, visit self, then go right

• Like eating a burger: left bun → meat (the focus) → right bun

Postorder = Visit Late: Wait for all children to finish, then visit self

• Like a parent: take care of kids first, consider yourself last

Why Preorder Doesn’t Need cur?

Preorder traversal actually doesn’t require a cur pointer because the visit order matches the DFS exploration order:

// Preorder concise version (Approach 1)
stack.push(root);
while (!stack.isEmpty()) {
    TreeNode node = stack.pop();
    result.add(node.val);        // Visit immediately on pop
    if (node.right != null) stack.push(node.right);
    if (node.left != null) stack.push(node.left);
}

But using the cur pointer (Approach 2) has benefits:

1. Unified mental model: All three traversals use the same framework
2. Easier memorization: Only need to remember timing differences
3. Better understanding: Clearly separates “exploration” from “visiting”

Practical Advice

Interview Scenarios:

• Only preorder: Use concise version (Approach 1) for shorter code
• Multiple traversals: Use unified template (Approach 2) to demonstrate deep understanding

Learning Recommendations:

1. First master each traversal’s independent implementation
2. Then learn the unified template to understand the essence
3. Choose the appropriate approach based on the scenario

LeetCode 144: Binary Tree Preorder Traversal (LC 144)

This is the classic problem for preorder traversal. All three solutions above directly solve it.

Example:

Input: root = [1,null,2,3]
    1
     \
      2
     /
    3

Output: [1, 2, 3]

Complexity Analysis

Method	Time	Space	Notes
Recursive	O(n)	O(h)	h = height, worst O(n) for skewed tree
Iterative	O(n)	O(h)	Explicit stack instead of call stack
Morris	O(n)	O(1)	Each edge traversed at most twice

Why Morris is O(n) Time?

Although there are nested loops, each edge is traversed at most twice:

1. Once when creating the thread
2. Once when removing the thread

Total: 2 × (n-1) edges = O(n)

Common Mistakes

1. Wrong Push Order (Iterative)

// WRONG: Left pushed first, processed last
if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right);

// CORRECT: Right first, left second
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);

2. Morris: Wrong Visit Timing

# WRONG for preorder: Visiting when thread exists
if predecessor.right:
    result.append(current.val)  # Too late!
    
# CORRECT: Visit BEFORE creating thread
if not predecessor.right:
    result.append(current.val)  # Visit now!
    predecessor.right = current

3. Forgetting Base Cases

// Don't forget null checks!
function preorder(root) {
  if (!root) return [];  // Essential!
  // ...
}

Edge Cases

1. Empty tree: Return []
2. Single node: Return [root.val]
3. Left-skewed tree: 1→2→3→4 (tests stack depth)
4. Right-skewed tree: Same as left-skewed
5. Complete binary tree: Standard case

Interview Tips

How to Explain

1. Start with recursive (easiest to understand)
2. Explain why stack simulates recursion
3. Mention Morris as O(1) space optimization
4. Discuss trade-offs (Morris modifies tree temporarily)

Follow-up Questions

• “Can you do it iteratively?” → Stack solution
• “Can you do it in O(1) space?” → Morris traversal
• “What if you can’t modify the tree?” → Stack is the best option
• “How would you handle a very deep tree?” → Morris prevents stack overflow

When NOT to Use Preorder

• Sorted order from BST: Use inorder (gives ascending order)
• Delete tree bottom-up: Use postorder
• Level-order traversal: Use BFS with queue

Summary

Aspect	Recursive	Iterative	Morris
Simplicity	⭐⭐⭐	⭐⭐	⭐
Space	O(h)	O(h)	O(1)
Modifies Tree	No	No	Yes (temporary)
Interview Use	Warmup	Standard	Show-off

Key Patterns to Remember:

1. Preorder = Root → Left → Right
2. Iterative: Push right, then left (LIFO)
3. Morris: Visit BEFORE going left
4. All methods are O(n) time

Master these three approaches, and you’ll handle any tree traversal question with confidence!