☕ DSA Java Articles

Topics › Binary Trees › Traversals

Preorder Traversal

Easy TUF ID 2790 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given the root of a binary tree, return the values of its nodes in preorder. Preorder means that every node is listed before anything below it: first the node, then its entire left subtree in preorder, then its entire right subtree in preorder. The tree may be empty and values may repeat.

Constraints (LeetCode 144): between 0 and 100 nodes, values in [-100, 100]. The Java file also runs a 5000-node chain and a 100000-node tree.

Example 1

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

1 comes first. Then the whole left subtree rooted at 2 is listed (2, 4, 5) before the right subtree rooted at 3 (3, 6).

Example 2

root = [1, null, 2, 3]      // 1 has a right child 2, and 2 has a left child 3
answer = [1, 2, 3]

1, then its right subtree: 2 first, then 2’s left child 3.

Preorder is the natural order whenever a parent must be handled before its children: copying a tree top-down, printing a directory listing, serializing a tree so it can be rebuilt (the first value read back is always the root), and rebuilding a tree from its preorder and inorder sequences.

Approach 1: Recursion

Intuition. Translate the definition directly: “preorder of a tree = the root, then preorder of the left subtree, then preorder of the right subtree”. The call stack remembers, for every node on the current path, that its right subtree still has to be visited once the left one returns.

Algorithm.

  1. If the node is null, return.
  2. Append the node’s value.
  3. Recurse into the left child.
  4. Recurse into the right child.
static List<Integer> recursive(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    preorder(root, out);
    return out;
}

static void preorder(TreeNode node, List<Integer> out) {
    if (node == null) return;
    out.add(node.val);              // 1. the node itself, before anything below it
    preorder(node.left, out);       // 2. its whole left subtree
    preorder(node.right, out);      // 3. then its whole right subtree
}

Complexity. Time O(n): each node is entered once, and each of the n + 1 null children costs one extra constant-time call. Space O(h) for the call stack, where h is the tree height: O(log n) when balanced, O(n) for a chain. On a very deep chain (around 10^5 nodes) the default Java stack can overflow, which is why the iterative form is worth knowing.

Approach 2: Iterative with an explicit stack

Intuition. Preorder is the easiest traversal to make iterative because a node is emitted the moment it is reached; nothing has to stay “pending” until later, unlike inorder. What we do need to remember is the work still waiting: after emitting a node we must handle its left subtree, then its right subtree. A stack is last-in-first-out, so we push the right child first and the left child second. The left child is then on top and gets processed next.

Why does the whole left subtree finish before the right child is popped? The right child sits directly below the left child in the stack. Everything pushed while the left subtree is being processed goes on top of the right child, so the right child cannot surface until every node of the left subtree has been popped. That is exactly “left subtree entirely before right subtree”.

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 and append its value.
    • Push its right child if present, then its left child if present.
  4. Return the list.
static List<Integer> iterative(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);
        if (node.right != null) stack.push(node.right);   // LIFO: pushed first, processed last
        if (node.left != null) stack.push(node.left);
    }
    return out;
}

Dry run on Example 1 (stack shown bottom to top):

step popped output so far pushed (right, then left) stack after
1 1 1 3, 2 [3, 2]
2 2 1, 2 5, 4 [3, 5, 4]
3 4 1, 2, 4 (none) [3, 5]
4 5 1, 2, 4, 5 (none) [3]
5 3 1, 2, 4, 5, 3 6 [6]
6 6 1, 2, 4, 5, 3, 6 (none) []

Complexity. Time O(n): each node is pushed and popped once. Space O(h): at any moment the stack holds the node being expanded plus at most one waiting right child for each node on the current path, so its size is bounded by the height plus one. For a balanced tree that is O(log n). A chain in either direction keeps the stack at size one, because each node has only one child to push. The stack grows only when many nodes on the current path each leave a right child waiting, and there can be at most h of those.

There is a second iterative style that mirrors the inorder loop: walk down the left spine, recording each node as you push it, then pop and move to the right child. It produces the same order and the same complexity. The version above is shorter and is the one most people remember.

If you need O(1) extra space, Morris preorder traversal threads the tree temporarily instead of using a stack.

Edge cases and pitfalls