Binary Tree Preorder Traversal

Description

144. Binary Tree Preorder Traversal

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]
Explanation:

Example 2:
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [1,2,4,5,6,7,3,8,9]
Explanation:

Example 3:
Input: root = []
Output: []

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

Constraints:

• The number of nodes in the tree is in the range $[0,100]$.
• $-100\le \text{Node.val}\le 100$

---

Approach 1: Recursive Traversal ($O(N)$ Time, $O(N)$ Space)

Intuition

Traverse the binary tree following the preorder sequence: Root node $\to$ Left subtree $\to$ Right subtree. Visit the current node by recording its value first, then recursively visit the left child, and finally the right child.

import java.util.ArrayList;
import java.util.List;
 
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) {
        if (node == null) return;
        result.add(node.val);
        preorder(node.left, result);
        preorder(node.right, result);
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Visits every node in the binary tree exactly once.
• Space Complexity: $O(N)$ worst-case call stack depth for a skewed tree ($O(\log N)$ for a balanced tree).

---

Approach 2: Iterative Stack (Unified Template — $O(N)$ Time, $O(N)$ Space)

Intuition

This approach uses the exact same structural template as iterative Inorder Traversal (curr pointer + inner/outer while loops with an explicit stack).

The only difference is when the node is visited:

• Preorder (Root $\to$ Left $\to$ Right): Record curr.val on the way down inside the inner while loop right before pushing curr to the stack and stepping left.
• Once the left branch is exhausted, pop the node to backtrack and move to its right child (curr = curr.right).

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
 
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode curr = root;
 
        while (curr != null || !stack.isEmpty()) {
            // Traverse left branch and visit nodes on the way down
            while (curr != null) {
                result.add(curr.val); // Preorder: Visit root before moving left
                stack.push(curr);
                curr = curr.left;
            }
 
            // Backtrack to parent and step into the right subtree
            curr = stack.pop();
            curr = curr.right;
        }
 
        return result;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Each node in the tree is visited, pushed, and popped exactly once.
• Space Complexity: $O(N)$ — Auxiliary space required for the explicit stack (ArrayDeque), bounded by the height of the tree ($O(N)$ for a skewed tree, $O(\log N)$ for a balanced tree).

---

Approach 3: Morris Preorder Traversal (Optimal — $O(N)$ Time, $O(1)$ Space)

Intuition

Achieve $O(1)$ auxiliary space using temporary tree threading:

1. If curr.left is null, record curr.val and step right (curr = curr.right).
2. Otherwise, find the in-order predecessor (rightmost node in the left subtree):
   • If pred.right is null, record curr.val before traversing left, set pred.right = curr (temporary thread), and move left (curr = curr.left).
   • If pred.right == curr, restore the tree structure by clearing pred.right = null and move right (curr = curr.right).

import java.util.ArrayList;
import java.util.List;
 
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        TreeNode curr = root;
 
        while (curr != null) {
            if (curr.left == null) {
                result.add(curr.val);
                curr = curr.right;
            } else {
                // Find in-order predecessor
                TreeNode pred = curr.left;
                while (pred.right != null && pred.right != curr) {
                    pred = pred.right;
                }
 
                if (pred.right == null) {
                    result.add(curr.val); // Visit root BEFORE creating thread and moving left
                    pred.right = curr;   // Temporary thread back to curr
                    curr = curr.left;
                } else {
                    pred.right = null;   // Restore original tree structure
                    curr = curr.right;
                }
            }
        }
 
        return result;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Each edge is traversed at most twice.
• Space Complexity: $O(1)$ auxiliary space — Modifies pointers in-place without recursion or extra data structures.

---

Easy Memory Rule

“Preorder pattern: Node $\to$ Left $\to$ Right. Push Right child then Left child onto stack so Left is visited first!”