5.14 Binary Tree Preorder Traversal

5.14.1 Problem Metadata

5.14.2 Description

Return the preorder traversal (root-left-right) of a binary tree.

5.14.3 Solution - Iterative Stack

5.14.3.1 Walkthrough

Push root to a stack. Pop, record value, then push right and left children (right first so left is processed next). Repeat until stack empty.

5.14.3.2 Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)

5.14.3.3 Code - Java

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

5.14.4 Solution - Recursive

5.14.4.1 Walkthrough

Recursively visit the current node first, then traverse left subtree, then right subtree. This mirrors the preorder definition and appends values in root-left-right order.

The recursive approach directly reflects the definition of pre-order traversal: 1. Base case: If node is null, return immediately 2. Process current: Add current node’s value to result 3. Recurse left: Visit all nodes in the left subtree 4. Recurse right: Visit all nodes in the right subtree

This is the natural traversal order for creating tree copies or serializing trees, as you process the parent before the children.

5.14.4.2 Analysis

  • Time Complexity: O(n) - Each node is visited exactly once
  • Space Complexity: O(h) - Recursion call stack depth where h is tree height (O(n) worst case for skewed tree)

5.14.4.3 Code - Java

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

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