☕ DSA Java Articles

Topics › Binary Trees › Traversals

Iterative Preorder Traversal of Binary Tree

Easy TUF ID 2872 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given the root of a binary tree, return its preorder traversal (the node, then its left subtree, then its right subtree) without using recursion. An empty tree gives an empty list.

Constraints: between 0 and 10^5 nodes, arbitrary 32-bit values, duplicates allowed. The tree may be a single chain 10^5 levels deep.

Trees are written in LeetCode’s level-order form, where null marks a missing child.

Example 1

          1
        /   \
       2     3
      / \   / \
     4   5 6   7
root = [1, 2, 3, 4, 5, 6, 7]
answer = [1, 2, 4, 5, 3, 6, 7]

Example 2

          1
        /   \
       2     3
        \   /
         4 5
          /
         6
root = [1, 2, 3, null, 4, 5, null, null, null, 6]
answer = [1, 2, 4, 3, 5, 6]     // 2 has only a right child, 3 only a left child

Why bother avoiding recursion? A recursive traversal uses one stack frame per level of the tree. On a balanced tree that is about log n frames, but on a chain it is n, and Java’s default thread stack overflows long before 10^5. An explicit stack lives on the heap and has no such limit. It also makes the traversal pausable, which is the basis of iterators over trees.

Approach 1: Recursion (the reference)

Intuition. Preorder is defined recursively: the root, then preorder of the left subtree, then preorder of the right subtree. This version is what the iterative methods must reproduce, and the tests compare them against it.

static List<Integer> recursive(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    preorder(root, out);
    return out;
}

private static void preorder(TreeNode node, List<Integer> out) {
    if (node == null) return;
    out.add(node.val);                        // Root
    preorder(node.left, out);                 // Left
    preorder(node.right, out);                // Right
}

Complexity. Time O(n), space O(h) on the call stack, where h is the height.

It is worth seeing what the call stack actually stores. While the recursion is inside the left subtree of a node, the frame of that node is suspended at the line preorder(node.left, out), and the only work still owed to it is preorder(node.right, out). So the call stack is really a list of “right subtrees still to do”. The iterative versions keep that list themselves.

Approach 2: One stack, push right then left

Intuition. Keep a stack of subtrees that still have to be traversed, with the one that must be done next on top. Pop a node: in preorder the node itself comes first, so output it right away. What remains for this node is “left subtree, then right subtree”. Because the stack is last-in-first-out, push the right child first and the left child second; the left child is now on top and its entire subtree will be processed (everything it pushes lands above the waiting right child) before the right child is popped.

Algorithm.

  1. If the root is null, return an empty list.
  2. Push the root.
  3. While the stack is not empty: pop a node, append its value, push its right child if present, then its left child if present.
static List<Integer> iterativeStack(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    if (root == null) return out;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        out.add(node.val);                                // visit as soon as the node is taken off
        if (node.right != null) stack.push(node.right);   // right waits underneath ...
        if (node.left != null) stack.push(node.left);     // ... left sits on top and is processed next
    }
    return out;
}

Dry run on Example 2. The stack is written bottom to top.

Step Popped Pushed Stack after Output so far
1 1 3, then 2 [3, 2] 1
2 2 4 (no left child) [3, 4] 1 2
3 4 nothing [3] 1 2 4
4 3 5 (no right child) [5] 1 2 4 3
5 5 6 [6] 1 2 4 3 5
6 6 nothing [] 1 2 4 3 5 6

Why it works. Invariant: the stack holds the roots of the subtrees that are still to be traversed, in the order they must be done from top to bottom, and the output so far is a prefix of the preorder. Popping a subtree root, outputting it, and replacing it with “left subtree, then right subtree” keeps that invariant, and the loop ends when nothing is left.

Complexity. Time O(n): each node is pushed and popped exactly once. Space O(h): the stack holds at most one pending right child for each node on the current path, plus the current left child.

Approach 3: Walk left, stack only the right children

Intuition. In Approach 2 the left child is pushed and then popped on the very next iteration, which is a wasted round trip. We can instead move to the left child directly and push only what genuinely has to wait: the right child. When the leftward walk falls off the tree, the most recent pending right subtree is the next thing to traverse.

This version has the same skeleton as the classic iterative inorder traversal (walk left, then resume from the stack), so learning it makes the other traversals easier to remember.

Algorithm.

  1. Set cur = root.
  2. While cur is not null or the stack is not empty:
    • If cur is null, pop the next pending right subtree into cur.
    • Append cur, push cur.right if it exists, and move to cur.left.
static List<Integer> iterativeRightStack(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    Deque<TreeNode> pendingRight = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !pendingRight.isEmpty()) {
        if (cur == null) cur = pendingRight.pop();        // left path ended: resume the latest unexplored right subtree
        out.add(cur.val);
        if (cur.right != null) pendingRight.push(cur.right);
        cur = cur.left;
    }
    return out;
}

Dry run on Example 2.

Step cur Action Pending stack Output so far
1 1 output, push 3, go left [3] 1
2 2 output, push 4, go left (null) [3, 4] 1 2
3 null → 4 pop 4, output, go left (null) [3] 1 2 4
4 null → 3 pop 3, output, go left [] 1 2 4 3
5 5 output, go left [] 1 2 4 3 5
6 6 output, go left (null) [] 1 2 4 3 5 6

At step 6 cur becomes null and the stack is empty, so the loop ends.

Complexity. Time O(n), each node visited once. Space O(h): the stack only ever holds right children of nodes on the current path. On a left-leaning tree it stays almost empty, while Approach 2 pushes and pops every node.

Comparing the three

  Recursion Push right then left Stack only right children
Extra memory call stack, O(h) heap stack, O(h) heap stack, O(h)
Survives a 10^5-deep chain not reliably yes yes
Stack operations none explicit one push and pop per node one push and pop per right child
Code shape definition “pop, emit, push children” same as iterative inorder

Edge cases and pitfalls