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]

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]

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 <= Node.val <= 100

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

Approach: Iterative with an Explicit Stack

Algorithm

1. In preorder traversal, visit the root first, then the left subtree, then the right subtree
2. Push the root onto a stack and loop while the stack is not empty
3. Pop a node, add its value to the result, then push its right child and then its left child onto the stack
4. Pushing the right child before the left child ensures the left child is popped first, preserving the correct order
5. Repeat until every node has been visited

Time & Space Complexity

• Time Complexity: O(n) - every node is pushed and popped exactly once
• Space Complexity: O(h) - the stack holds at most one path plus pending siblings, O(n) in the worst case for a skewed tree

Java Implementation

import java.util.ArrayList;
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.List;

public class BinaryTreePreorderTraversal {

    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return result;
    }

    public static 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;
        }
    }

    // Test method
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        System.out.println("Input: root = [1,null,2,3]");
        System.out.println("Output: " + preorderTraversal(root)); // Expected: [1, 2, 3]
    }
}

Recursive Implementation

public List<Integer> preorderTraversalRecursive(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    helper(root, result);
    return result;
}

private void helper(TreeNode node, List<Integer> result) {
    if (node == null) {
        return;
    }
    result.add(node.val);
    helper(node.left, result);
    helper(node.right, result);
}

Example Walkthrough

For root = [1, null, 2, 3]:

1. Push 1. Pop 1 -> result [1], push right 2, push left (null)
2. Pop 2 -> result [1, 2], push right (null), push left 3
3. Pop 3 -> result [1, 2, 3]
4. Stack empty, return [1, 2, 3]

Key Points

1. Visit-First Order: The node value is added the moment it is popped, before its children
2. Right-Before-Left Push: Pushing the right child first keeps the left child on top of the stack
3. Iterative vs Recursive: The explicit stack mirrors the call stack of the recursive version
4. Edge Cases: An empty tree returns an empty list; a single node returns its own value
5. O(n) Time: Every node is processed exactly once