143. Binary Tree Preorder Traversal

🔗 LeetCode Problem: 144. Binary Tree Preorder Traversal
📊 Difficulty: Easy
🏷️ Topics: Binary Trees, DFS, Traversal, Stack, Recursion

Problem Statement

Given the root of a binary tree, return the preorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3]
Output: [1,2,3]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Follow up: Recursive solution is trivial, could you do it iteratively?

Constraints: - The number of nodes in the tree is in the range [0, 100] - -100 <= Node.val <= 100

---

🌳 Visual Understanding - The Three DFS Orders!

Quick Recap: The Three Orders

Tree:
       1
      / \
     2   3
    / \
   4   5

PREORDER (Root → Left → Right):
  Process: 1 → 2 → 4 → 5 → 3
  Pattern: Visit root FIRST! 🎯
  Result: [1, 2, 4, 5, 3]

INORDER (Left → Root → Right):
  Process: 4 → 2 → 5 → 1 → 3
  Pattern: Visit root in MIDDLE
  Result: [4, 2, 5, 1, 3]

POSTORDER (Left → Right → Root):
  Process: 4 → 5 → 2 → 3 → 1
  Pattern: Visit root LAST
  Result: [4, 5, 2, 3, 1]

ONLY difference: When we process the root! ⚡

Preorder Visual Breakdown:

Tree:
       1           ← Process root FIRST: [1]
      / \
     2   3         ← Then go left: [1, 2]
    / \
   4   5          ← Complete left subtree: [1, 2, 4, 5]
                  ← Then right: [1, 2, 4, 5, 3]

Order of processing:
  1 (root) → 2 (left) → 4 (left-left) → 5 (left-right) → 3 (right)

Think: "Visit nodes as you ENCOUNTER them"
Top-down, left-to-right! 📊

Comparison with Problem 139 (Inorder):

Same tree:       1
                / \
               2   3

INORDER (Problem 139):
  [2, 1, 3]
  Visit left BEFORE processing root

PREORDER (Problem 143):
  [1, 2, 3]
  Process root BEFORE visiting left

Just moved ONE line in code! 🎯

---

🧠 The AHA Moment - Root First!

Why "Pre"-order?

"PRE" = BEFORE

We process the root BEFORE (pre) its children!

Visual path:
       1  ← Process immediately! (pre)
      / \
     2   3

Then recursively do same for subtrees:
     2  ← Process immediately! (pre)
      \
       3

Real-World Use Cases:

1. Tree Copying:
   - Need parent before children
   - Create node, then copy children
   - Preorder perfect! ✓

2. Expression Trees:
   - Prefix notation
   - Operator before operands
   - Example: + 1 2 = 1 + 2

3. File System Traversal:
   - Process directory before contents
   - mkdir parent, then create files
   - Preorder naturally does this!

4. Tree Serialization:
   - Save parent first
   - Then recursively save children
   - Problem 142 (Flatten) used this!

---

🧠 Recursive Thinking - Building the Solution

Base Case:

Simplest tree?
  → null (empty)

What to do?
  → Nothing! Return.

if (node == null) return;

Recursive Case:

For any node:
  1. Process ROOT (add to result)
  2. Recurse on LEFT subtree
  3. Recurse on RIGHT subtree

This IS preorder!

The Template:

preorder(node, result):
  if node is null:
    return

  // ROOT (process first!)
  result.add(node.val)

  // LEFT
  preorder(node.left, result)

  // RIGHT
  preorder(node.right, result)

---

🎯 Solution 1: Recursive (Elegant!)

Implementation:

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorder(root, result);
        return result;
    }

    private void preorder(TreeNode node, List<Integer> result) {
        // Base Case: null node
        if (node == null) {
            return;
        }

        // ROOT: Process current node FIRST
        // WHY? Preorder visits root before children!
        result.add(node.val);

        // LEFT: Recursively traverse left subtree
        preorder(node.left, result);

        // RIGHT: Recursively traverse right subtree
        preorder(node.right, result);
    }
}

Compare with Inorder (Problem 139):

// INORDER:
private void inorder(TreeNode node, List<Integer> result) {
    if (node == null) return;

    inorder(node.left, result);   // LEFT
    result.add(node.val);          // ROOT (middle)
    inorder(node.right, result);   // RIGHT
}

// PREORDER:
private void preorder(TreeNode node, List<Integer> result) {
    if (node == null) return;

    result.add(node.val);          // ROOT (first!) ⚡
    preorder(node.left, result);   // LEFT
    preorder(node.right, result);  // RIGHT
}

// ONE line moved = different traversal!

---

🎯 Solution 2: Iterative with Stack

The Strategy:

Preorder processes root FIRST

Stack strategy:
  1. Push root to stack
  2. While stack not empty:
     a. Pop node
     b. Process it (add to result)
     c. Push RIGHT child (if exists)
     d. Push LEFT child (if exists)

Why push RIGHT before LEFT?
  → Stack is LIFO
  → Want to process LEFT first
  → So LEFT must be on top!

Implementation:

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        if (root == null) {
            return result;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            // Pop and process node
            TreeNode node = stack.pop();
            result.add(node.val);

            // Push children (RIGHT first, then LEFT)
            // WHY? Stack is LIFO - want LEFT processed first
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }

        return result;
    }
}

Why This Works:

Tree:    1
        / \
       2   3

Stack operations:
  Initial: [1]

  Pop 1, process: [1]
    Push 3: [3]
    Push 2: [3, 2]

  Pop 2, process: [1, 2]
    No children

  Pop 3, process: [1, 2, 3]
    No children

  Done! Result: [1, 2, 3] ✓

LEFT processed before RIGHT because:
  LEFT pushed last → on top → popped first!

---

🔍 Detailed Dry Run - Recursive

Tree:
       1
      / \
     2   3
    / \
   4   5

Complete Recursion Flow:

CALL STACK VISUALIZATION:

Level 0: preorder(1, [])
│
├─ node = 1, not null
├─ ROOT: result.add(1) → [1]
│
├─ LEFT: preorder(2, [1]) ──────────────────┐
│                                            │
│  Level 1: preorder(2, [1])                │
│  │                                         │
│  ├─ node = 2, not null                   │
│  ├─ ROOT: result.add(2) → [1, 2]         │
│  │                                         │
│  ├─ LEFT: preorder(4, [1, 2]) ─────────┐ │
│  │                                      │ │
│  │  Level 2: preorder(4, [1, 2])       │ │
│  │  │                                   │ │
│  │  ├─ node = 4, not null              │ │
│  │  ├─ ROOT: result.add(4) → [1,2,4]   │ │
│  │  │                                   │ │
│  │  ├─ LEFT: preorder(null) → return   │ │
│  │  ├─ RIGHT: preorder(null) → return  │ │
│  │  └─ return                           │ │
│  │                                      │ │
│  ├─ RIGHT: preorder(5, [1, 2, 4]) ────┐│ │
│  │                                     ││ │
│  │  Level 2: preorder(5, [1,2,4])     ││ │
│  │  │                                  ││ │
│  │  ├─ node = 5, not null             ││ │
│  │  ├─ ROOT: result.add(5) → [1,2,4,5]││ │
│  │  │                                  ││ │
│  │  ├─ LEFT: preorder(null) → return  ││ │
│  │  ├─ RIGHT: preorder(null) → return ││ │
│  │  └─ return                          ││ │
│  │                                     ││ │
│  └─ return                             │ │
│                                         │
├─ RIGHT: preorder(3, [1, 2, 4, 5]) ────────┐
│                                            │
│  Level 1: preorder(3, [1,2,4,5])         │
│  │                                         │
│  ├─ node = 3, not null                   │
│  ├─ ROOT: result.add(3) → [1,2,4,5,3]   │
│  │                                         │
│  ├─ LEFT: preorder(null) → return        │
│  ├─ RIGHT: preorder(null) → return       │
│  └─ return                                │
│                                            │
└─ FINAL: [1, 2, 4, 5, 3]                  │

Result: [1, 2, 4, 5, 3]

Order of Processing:

Visit order matches result order!

1. Visit 1 → add 1 → [1]
2. Visit 2 → add 2 → [1, 2]
3. Visit 4 → add 4 → [1, 2, 4]
4. Visit 5 → add 5 → [1, 2, 4, 5]
5. Visit 3 → add 3 → [1, 2, 4, 5, 3]

Process nodes as we ENCOUNTER them!
Top-down, left-to-right! 📊

---

🔍 Detailed Dry Run - Iterative

Tree:
       1
      / \
     2   3
    /
   4

Stack Operations:

INITIAL:
  stack = [1]
  result = []

═══════════════════════════════════════
ITERATION 1:
═══════════════════════════════════════

Pop: node = 1
Process: result.add(1) → [1]

Push children:
  1.right = 3 → push(3)
  1.left = 2 → push(2)

State:
  stack = [3, 2]  (bottom to top)
  result = [1]

═══════════════════════════════════════
ITERATION 2:
═══════════════════════════════════════

Pop: node = 2 (top of stack)
Process: result.add(2) → [1, 2]

Push children:
  2.right = null (skip)
  2.left = 4 → push(4)

State:
  stack = [3, 4]
  result = [1, 2]

═══════════════════════════════════════
ITERATION 3:
═══════════════════════════════════════

Pop: node = 4
Process: result.add(4) → [1, 2, 4]

Push children:
  4.right = null (skip)
  4.left = null (skip)

State:
  stack = [3]
  result = [1, 2, 4]

═══════════════════════════════════════
ITERATION 4:
═══════════════════════════════════════

Pop: node = 3
Process: result.add(3) → [1, 2, 4, 3]

Push children:
  3.right = null (skip)
  3.left = null (skip)

State:
  stack = []
  result = [1, 2, 4, 3]

═══════════════════════════════════════
DONE! Stack empty.
═══════════════════════════════════════

FINAL: [1, 2, 4, 3]

---

📊 The Complete DFS Family

All Three Traversals:

// PREORDER (Root → Left → Right)
private void preorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    result.add(node.val);          // ROOT first
    preorder(node.left, result);   // LEFT
    preorder(node.right, result);  // RIGHT
}

// INORDER (Left → Root → Right)
private void inorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    inorder(node.left, result);    // LEFT
    result.add(node.val);          // ROOT middle
    inorder(node.right, result);   // RIGHT
}

// POSTORDER (Left → Right → Root)
private void postorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    postorder(node.left, result);  // LEFT
    postorder(node.right, result); // RIGHT
    result.add(node.val);          // ROOT last
}

Visual Comparison:

Tree:
       1
      / \
     2   3
    / \
   4   5

PREORDER:  [1, 2, 4, 5, 3]  (Root first)
           └┘ └──────┘ └┘
          root  left   right

INORDER:   [4, 2, 5, 1, 3]  (Root middle)
           └──────┘ └┘ └┘
             left  root right

POSTORDER: [4, 5, 2, 3, 1]  (Root last)
           └──────┘ └┘ └┘
             left  right root

Same recursion structure!
Only position of result.add() changes! ⚡

---

📊 Complexity Analysis

Recursive Solution:

Time Complexity: O(n)

Visit each node exactly once
Process each: O(1) operation
Total: n × O(1) = O(n)

Space Complexity: O(h)

Recursion call stack: O(h) where h = height

Best case (balanced): O(log n)
Worst case (skewed): O(n)

Iterative Solution:

Time Complexity: O(n)

Same - visit each node once
Each push and pop: O(1)
Total: O(n)

Space Complexity: O(h)

Stack size: O(h) where h = height

Best case (balanced): O(log n)
Worst case (skewed): O(n)

Same space as recursive!

---

⚠️ Common Mistakes

Mistake 1: Wrong Order in Iterative

// ❌ WRONG - Pushes LEFT before RIGHT
if (node.left != null) {
    stack.push(node.left);
}
if (node.right != null) {
    stack.push(node.right);   // On top!
}

// RIGHT pops first! Wrong order: [1, 3, 2]

// ✓ CORRECT - Push RIGHT first
if (node.right != null) {
    stack.push(node.right);   // Goes in first
}
if (node.left != null) {
    stack.push(node.left);    // On top!
}

// LEFT pops first! Correct: [1, 2, 3]

Mistake 2: Processing After Recursion

// ❌ WRONG - This is POSTORDER!
private void preorder(TreeNode node, List<Integer> result) {
    if (node == null) return;

    preorder(node.left, result);
    preorder(node.right, result);
    result.add(node.val);  // After children = POSTORDER!
}

// ✓ CORRECT - Process BEFORE recursion
result.add(node.val);      // Before children = PREORDER!
preorder(node.left, result);
preorder(node.right, result);

Mistake 3: Not Checking Null Before Push

// ❌ WRONG - Pushes null nodes
stack.push(node.right);  // Might be null!
stack.push(node.left);   // Might be null!

// Later: node = stack.pop() → node is null → NPE!

// ✓ CORRECT - Check before pushing
if (node.right != null) {
    stack.push(node.right);
}
if (node.left != null) {
    stack.push(node.left);
}

---

🎯 Pattern Recognition - DFS Traversal Template

Universal DFS Template:

// Recursive version
private void dfs(TreeNode node, List<Integer> result) {
    if (node == null) return;

    // PREORDER: process here
    // result.add(node.val);

    dfs(node.left, result);

    // INORDER: process here
    result.add(node.val);

    dfs(node.right, result);

    // POSTORDER: process here
    // result.add(node.val);
}

// Just uncomment the one you need!

Iterative Template (Preorder):

Stack<TreeNode> stack = new Stack<>();
stack.push(root);

while (!stack.isEmpty()) {
    TreeNode node = stack.pop();

    // Process node (preorder)
    process(node);

    // Push children (right first!)
    if (node.right != null) stack.push(node.right);
    if (node.left != null) stack.push(node.left);
}

Related Problems:

1. Binary Tree Inorder Traversal (Problem 139)

Same structure, different position
Move result.add() to middle

2. Binary Tree Postorder Traversal

Same structure, different position
Move result.add() to end

3. Flatten Binary Tree (Problem 142)

Uses preorder traversal
Flattened order = preorder!

4. Validate Binary Search Tree

Uses inorder traversal
BST inorder is sorted

5. Delete Nodes and Return Forest

Uses postorder traversal
Process children before parent

When to Use Each:

PREORDER:
  ✓ Tree copying/cloning
  ✓ Serialization
  ✓ Expression evaluation (prefix)
  ✓ Creating tree structure

INORDER:
  ✓ BST operations (sorted order!)
  ✓ BST validation
  ✓ Expression evaluation (infix)

POSTORDER:
  ✓ Tree deletion
  ✓ Calculate tree properties
  ✓ Expression evaluation (postfix)
  ✓ Dependency resolution

---

📝 Quick Revision Notes

🎯 Core Concept

Preorder = Root → Left → Right. Process root FIRST, then recursively process left and right subtrees. Recursive: just put result.add(node.val) BEFORE recursion calls. Iterative: use stack, push RIGHT before LEFT (so LEFT pops first). Used for tree copying, serialization, and when parent must be processed before children.

⚡ Quick Implementation

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public static TreeNode buildTree(Integer[] arr) {
        if (arr == null || arr.length == 0 || arr[0] == null) {
            return null;
        }

        TreeNode root = new TreeNode(arr[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int i = 1;
        while (!queue.isEmpty() && i < arr.length) {
            TreeNode current = queue.poll();

            // Process left child
            if (i < arr.length) {
                if (arr[i] != null) {
                    current.left = new TreeNode(arr[i]);
                    queue.offer(current.left);
                }
                i++;
            }

            // Process right child
            if (i < arr.length) {
                if (arr[i] != null) {
                    current.right = new TreeNode(arr[i]);
                    queue.offer(current.right);
                }
                i++;
            }
        }

        return root;
    }

    public static void print(TreeNode root) {
        if (root == null) {
            System.out.println("[]");
            return;
        }

        List<String> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                result.add(String.valueOf(node.val));
                queue.offer(node.left);
                queue.offer(node.right);
            } else {
                result.add("null");
            }
        }

        while (!result.isEmpty() && result.get(result.size() - 1).equals("null")) {
            result.remove(result.size() - 1);
        }

        System.out.println(result);
    }    
}

class Solution {
  public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();

    if(root == null) {
      return res;
    }

    // // Approach 1 - recursion
    // recursiveDFS(root, res);

    // Approach 2 - stack based
    iterativeDFS(root, res);

    return res;
  }

  private void iterativeDFS(TreeNode root, List<Integer> res) {
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
      TreeNode curr = stack.pop();
      res.add(curr.val);

      if(curr.right != null) {
        stack.push(curr.right);
      }      

      if(curr.left != null) {
        stack.push(curr.left);
      }
    }
  }

  private void recursiveDFS(TreeNode root, List<Integer> res) {
    // root, left, right
    if(root == null) {
      return;
    }

    res.add(root.val);
    recursiveDFS(root.left, res);
    recursiveDFS(root.right, res);
  }

  public static void main(String[] args) {
    Solution s = new Solution();

    System.out.println(s.preorderTraversal(TreeNode.buildTree(new Integer[] {1,null,2,3}))); // 1,2,3
    System.out.println(s.preorderTraversal(TreeNode.buildTree(new Integer[] {1,2,3,4,5,null,8,null,null,6,7,9}))); // 1,2,4,5,6,7,3,8,9
    System.out.println(s.preorderTraversal(TreeNode.buildTree(new Integer[] {}))); // empty
    System.out.println(s.preorderTraversal(TreeNode.buildTree(new Integer[] {1}))); // 1
  }
}

🔑 Key Insights

The One-Line Difference:

PREORDER vs INORDER:

// Preorder:
result.add(node.val);          // Before recursion
preorder(node.left, result);
preorder(node.right, result);

// Inorder:
inorder(node.left, result);
result.add(node.val);          // Between recursion
inorder(node.right, result);

ONE line moved = different order! 🎯

Stack Push Order:

Why push RIGHT before LEFT?

Stack is LIFO (Last In, First Out):
  Push RIGHT → Push LEFT
  [RIGHT, LEFT]  (bottom to top)

  Pop LEFT first (top)
  Pop RIGHT second

  Result: LEFT → RIGHT ✓

Push LEFT first would give: RIGHT → LEFT ✗

When to Use Preorder:

Ask: "Need parent before children?"

  YES → Preorder!

  Examples:
    - Copying tree (create parent first)
    - Serializing (save parent first)
    - Creating structure (parent exists first)

  NO → Consider inorder or postorder

🎪 Memory Aid

"PRE = BEFORE children!"
"Process as you encounter!"
"Stack: RIGHT then LEFT!"
"Top-down traversal!" ✨

⚠️ Don't Forget

• Process BEFORE recursion (that's what PRE means!)
• Push RIGHT before LEFT (in iterative version!)
• Check null before push (don't push nulls to stack!)
• Same as Problem 139 (just move one line!)
• Useful for copying (parent before children!)
• Result order = visit order (unlike inorder!)

---

🎉 Congratulations!

You've completed the DFS traversal trilogy!

What You Learned:

✅ Preorder pattern - Root → Left → Right
✅ Recursive solution - Process before recursion
✅ Iterative with stack - RIGHT before LEFT
✅ All three DFS orders - Preorder, Inorder, Postorder
✅ When to use each - Based on problem needs
✅ One template - Three variations

The DFS Mastery:

You now master ALL three DFS traversals:

Problem 139: Inorder (Left → Root → Right)
  ✓ For BST (sorted order)
  ✓ Root in middle

Problem 143: Preorder (Root → Left → Right)
  ✓ For copying (parent first)
  ✓ Root before children

Next: Postorder (Left → Right → Root)
  ✓ For deletion (children first)
  ✓ Root after children

One structure → Three orders! 🎯

Interview Readiness:

Any DFS traversal question:
  1. Identify which order needed ✓
  2. Position result.add() correctly ✓
  3. Code recursive in 2 minutes ✓
  4. Code iterative in 5 minutes ✓

You're a DFS expert! 💪

You've mastered tree traversals! 🌳✨