Iterative pre-order traversal of a binary tree

You are fifteen minutes into a phone screen and the interviewer asks you to traverse a binary tree in pre-order, but without recursion. This problem, also known as Binary Tree Preorder Traversal on LeetCode and other platforms, tests whether you understand how the call stack works and can replicate it with an explicit data structure. It is a staple in technical interviews because it bridges the gap between recursive thinking and iterative control flow.

TL;DR

Push the root onto a stack. While the stack is not empty, pop a node, record its value, then push its right child followed by its left child. The left child ends up on top of the stack and gets processed first, which preserves pre-order semantics (root, left, right). The algorithm runs in O(n) time and O(log n) space for a balanced tree.

Why This Problem Matters

Iterative tree traversal shows up constantly in interviews for a simple reason: it forces you to think about what recursion is actually doing under the hood. When you write a recursive pre-order function, the compiler manages a call stack for you. The iterative version makes you manage that stack yourself. Once you internalize this pattern, converting any recursive tree algorithm to an iterative one becomes straightforward.

Binary Trees and Traversal Orders

A binary tree is a hierarchical structure where each node has at most two children. There are three classic depth-first traversal orders:

• Pre-order: root, left subtree, right subtree
• In-order: left subtree, root, right subtree
• Post-order: left subtree, right subtree, root

Here is a complete binary tree with seven nodes to illustrate the differences:

For the tree above:

• Pre-order visits: [1, 2, 4, 5, 3, 6, 7]
• In-order visits: [4, 2, 5, 1, 6, 3, 7]
• Post-order visits: [4, 5, 2, 6, 7, 3, 1]

Pre-order is the most natural to implement iteratively because the root is always processed first, before descending into subtrees.

Understanding the Problem

Given: The root node of a binary tree. Return: A list of node values in pre-order (root, left, right). Constraint: Do not use recursion.

Here is the example tree from the problem:

The pre-order traversal of this tree produces [1, 2, 3, 4, 5]. Node 1 is visited first (root), then 2 (left subtree), then 3 (right subtree root), then 4 and 5 (children of 3).

Edge Cases

1. Null root: Return an empty list.
2. Single node: Return a list with just that node's value.
3. Left-skewed tree (every node only has a left child): The stack never holds more than one element at a time.
4. Right-skewed tree (every node only has a right child): Same behavior as left-skewed, just mirrored.

The Key Insight: Stack as Call Stack Replacement

When a recursive pre-order function processes a node, it does three things in order:

1. Records the current node's value
2. Calls itself on the left child
3. Calls itself on the right child

The second call (left) runs before the third (right) because function calls block until they return. A stack gives us this same behavior. If we push the right child before the left child, the left child sits on top of the stack and gets popped first.

That single observation is the entire algorithm.

Solution Approach

Let me walk through the algorithm step by step using our example tree [1, 2, 3, # , #, 4, 5].

Prefer a different language? Jump to solutions in other languages.

Step-by-Step Stack Trace

Here is how the stack and output evolve at each iteration:

1. Initialize: Push root (1) onto the stack.
2. Pop 1: Add 1 to output. Push right child 3, then left child 2. Stack: [3, 2].
3. Pop 2: Add 2 to output. No children. Stack: [3].
4. Pop 3: Add 3 to output. Push right child 5, then left child 4. Stack: [5, 4].
5. Pop 4: Add 4 to output. No children. Stack: [5].
6. Pop 5: Add 5 to output. No children. Stack: [].
7. Done: Stack is empty. Return [1, 2, 3, 4, 5].

Notice how pushing right before left guarantees that the left subtree is fully explored before any right sibling is touched.

Implementation

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

public class Solution {
  public List<Integer> preOrder(TreeNode root) {
    // Create the output list
    List<Integer> out = new ArrayList<>();

    // Handle the empty tree case
    if (root == null) return out;

    // Use a Deque as a stack
    Deque<TreeNode> stack = new LinkedList<>();
    stack.push(root);

    while (!stack.isEmpty()) {
      // Pop the top node and record its value
      TreeNode node = stack.pop();
      out.add(node.data);

      // Push right child first so left child is processed first
      if (node.right != null) stack.push(node.right);
      if (node.left != null) stack.push(node.left);
    }

    return out;
  }
}

Let me trace through the animated traversal to reinforce this:

The algorithm processes each node exactly once. The push order (right before left) is the only non-obvious detail. Everything else follows directly from how stacks work.

Complexity Analysis

Time Complexity: O(n)

Every node is pushed onto the stack once and popped once. Each push and pop is O(1). With n nodes total, the work is O(n). This holds regardless of tree shape - balanced, skewed, or anything in between.

Space Complexity: O(h) where h is the height

The stack holds at most O(h) nodes at any point. In a balanced tree, h is roughly log(n), so the space is O(log n). In a completely skewed tree, h equals n, so the worst case is O(n).

Compare this with the recursive approach: recursion also uses O(h) space, but that space lives on the system call stack, which has a fixed limit. The iterative approach allocates from the heap, giving you much more room before running into limits.

Why Not Recursion?

The recursive version is shorter:

public List<Integer> preOrderRecursive(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    result.add(root.data);
    result.addAll(preOrderRecursive(root.left));
    result.addAll(preOrderRecursive(root.right));
    return result;
}

But it has a practical drawback: on deeply nested trees (thousands of levels), the system stack can overflow. The iterative version handles arbitrarily deep trees because the stack lives on the heap. Interviewers ask for the iterative version specifically to see if you understand this distinction.

Common Pitfalls

1. Pushing left before right: This produces root-right-left order instead of root-left-right. The right child must be pushed first.

2. Forgetting the null check before pushing: Pushing a null child onto the stack and then trying to access its data throws a NullPointerException on the next pop.

3. Using a Queue instead of a Stack: A queue gives you level-order (BFS) traversal, not depth-first pre-order. The LIFO behavior of a stack is essential.

4. Returning inside the loop: Some candidates try to return early when both children are null. The loop termination condition (!stack.isEmpty()) handles this naturally.

Interview Tips

When solving this in an interview:

• Clarify the traversal order: Pre-order means root first, then left, then right. Confirm with the interviewer.
• State the constraint explicitly: "Since we cannot use recursion, I will simulate the call stack with a Deque used as a stack."
• Draw the tree: Sketch the example tree and trace through two or three iterations showing the stack contents. This demonstrates your thought process clearly.
• Mention the push order: "I push right before left because the stack is LIFO, so left will be popped and processed first."
• Discuss complexity proactively: Mentioning O(n) time and O(h) space before the interviewer asks shows depth of understanding.

Traversal Order Comparison

To solidify your understanding, here is how the three depth-first traversals differ in their iterative implementations:

Pre-order has the simplest iterative implementation. In-order requires tracking whether to go left or process the current node. Post-order is the trickiest because the root is processed last.

Solutions in Other Languages

Python

from collections import deque

class Solution:
    def pre_order(self, root):
        out = []
        if root is None:
            return out

        stack = deque()
        stack.append(root)

        while len(stack) > 0:
            node = stack.pop()
            out.append(node.data)
            if node.right is not None:
                stack.append(node.right)
            if node.left is not None:
                stack.append(node.left)

        return out

JavaScript

class Solution {
  preOrder(root) {
    const out = [];
    if (root === null) return out;

    const stack = [];
    stack.push(root);

    while (stack.length > 0) {
      const node = stack.pop();
      out.push(node.data);
      if (node.right !== null) stack.push(node.right);
      if (node.left !== null) stack.push(node.left);
    }

    return out;
  }
}

TypeScript

class Solution {
  preOrder(root: TreeNode | null): number[] {
    const out: number[] = [];
    if (root === null) return out;

    const stack: TreeNode[] = [];
    stack.push(root);

    while (stack.length > 0) {
      const node = stack.pop()!;
      out.push(node.data);
      if (node.right !== null) stack.push(node.right);
      if (node.left !== null) stack.push(node.left);
    }

    return out;
  }
}

C++

#include <vector>
#include <stack>

class Solution {
public:
  std::vector<int> preOrder(TreeNode *root) {
    std::vector<int> out;
    if (root == nullptr) return out;

    std::stack<TreeNode *> stack;
    stack.push(root);

    while (!stack.empty()) {
      TreeNode *node = stack.top();
      stack.pop();
      out.push_back(node->data);
      if (node->right != nullptr) stack.push(node->right);
      if (node->left != nullptr) stack.push(node->left);
    }

    return out;
  }
};

Scala

import scala.collection.mutable

class Solution {
  def preOrder(root: TreeNode): List[Int] = {
    val out = mutable.ListBuffer[Int]()
    if (root == null) return out.toList

    val stack = new mutable.Stack[TreeNode]
    stack.push(root)

    while (stack.nonEmpty) {
      val node = stack.pop
      out.append(node.data)
      if (node.right != null) stack.push(node.right)
      if (node.left != null) stack.push(node.left)
    }

    out.toList
  }
}

Kotlin

import java.util.ArrayDeque

class Solution {
  fun preOrder(root: TreeNode?): List<Int> {
    val out = mutableListOf<Int>()
    if (root == null) return out

    val stack = ArrayDeque<TreeNode>()
    stack.push(root)

    while (stack.isNotEmpty()) {
      val node = stack.pop()
      out.add(node.data)
      if (node.right != null) stack.push(node.right)
      if (node.left != null) stack.push(node.left)
    }

    return out
  }
}

Swift

class Solution {
    func preOrder(_ root: TreeNode?) -> [Int] {
        var out: [Int] = []
        if root == nil { return out }

        var stack: [TreeNode] = []
        stack.append(root!)

        while !stack.isEmpty {
            let node = stack.removeLast()
            out.append(node.data)
            if node.right != nil { stack.append(node.right!) }
            if node.left != nil { stack.append(node.left!) }
        }

        return out
    }
}

Ruby

class Solution
  def pre_order(root)
    out = []
    return out if root.nil?

    stack = []
    stack.push(root)

    until stack.empty?
      node = stack.pop
      out.push(node.data)
      stack.push(node.right) unless node.right.nil?
      stack.push(node.left) unless node.left.nil?
    end

    out
  end
end

Rust

impl Solution {
    pub fn pre_order(&self, root: Option<Box<TreeNode>>) -> Vec<i32> {
        let mut out = Vec::new();
        if root.is_none() {
            return out;
        }

        let mut stack: Vec<Box<TreeNode>> = Vec::new();
        stack.push(root.unwrap());

        while let Some(node) = stack.pop() {
            out.push(node.data);
            if let Some(right) = node.right {
                stack.push(right);
            }
            if let Some(left) = node.left {
                stack.push(left);
            }
        }

        out
    }
}

Dart

class Solution {
  List<int> preOrder(TreeNode? root) {
    List<int> out = [];
    if (root == null) return out;

    List<TreeNode> stack = [];
    stack.add(root);

    while (stack.isNotEmpty) {
      TreeNode node = stack.removeLast();
      out.add(node.data);
      if (node.right != null) stack.add(node.right!);
      if (node.left != null) stack.add(node.left!);
    }

    return out;
  }
}

PHP

class Solution {
    public function preOrder(?TreeNode $root): array {
        $out = [];
        if ($root === null) return $out;

        $stack = [$root];

        while (!empty($stack)) {
            $node = array_pop($stack);
            $out[] = $node->data;
            if ($node->right !== null) $stack[] = $node->right;
            if ($node->left !== null) $stack[] = $node->left;
        }

        return $out;
    }
}

C#

public class Solution {
    public List<int> preOrder(TreeNode? root) {
        var result = new List<int>();
        if (root == null) return result;

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

        while (stack.Count > 0) {
            var node = stack.Pop();
            result.Add(node.data);
            if (node.right != null) stack.Push(node.right);
            if (node.left != null) stack.Push(node.left);
        }

        return result;
    }
}

Key Takeaways

• Iterative pre-order uses a stack to replace the call stack. Push the root, then loop: pop, record, push right, push left.
• The push order matters. Right before left ensures left subtrees are processed first, matching pre-order semantics.
• Time is O(n) because each node is pushed and popped exactly once. Space is O(h) where h is the tree height.
• The iterative approach handles deeply nested trees without stack overflow, which is the practical reason interviewers ask for it over the recursive version.
• This pattern generalizes: once you can convert pre-order to iterative, in-order and post-order follow similar reasoning with slightly more bookkeeping.

Practice Makes Perfect

Once you are comfortable with iterative pre-order, try these related problems to deepen your tree traversal skills:

• Iterative in-order traversal (requires the "go left" pattern)
• Iterative post-order traversal (the trickiest of the three)
• Level-order traversal with a queue (BFS instead of DFS)
• Height of a binary tree (recursive, but builds on the same structural understanding)

Remember, consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Whether you are just starting out or targeting your dream role, mastering iterative tree traversals will pay dividends across dozens of interview questions.