LeetCode 144 – Binary Tree Preorder Traversal

Preorder is the easiest of the three traversals to write iteratively, and it is worth doing right after inorder precisely because the contrast explains why. One traversal needs a descend-then-backtrack loop; this one is a plain stack with no bookkeeping at all — and the reason is a single property of the visit order.

The problem

Return the preorder traversal of a binary tree's values: node, then left subtree, then right subtree.

    1
     \          -> [1, 2, 3]
      2
     /
    3

    4
   / \        -> [4, 2, 1, 3, 6, 5, 7]
  2   6
 / \ / \
1  3 5  7

[]   -> []
[1]  -> [1]

Why this one is easy

In preorder a node is visited the moment you arrive at it, before either child. So the instant you pop a node you can emit it and forget it — there is nothing to come back for.

Inorder cannot do that: it must visit the entire left subtree first, so a node has to be remembered while its left side is explored and revisited afterwards. That is what forces the descend-left inner loop there and what makes it the harder code.

preorder   arrive -> emit -> done with this node
inorder    arrive -> remember -> explore left -> come back -> emit
postorder  arrive -> remember -> explore both -> come back -> emit

Say that out loud; it is the whole reason the three iterative versions differ in difficulty.

Push right before left

A stack reverses what you put into it, so children go on in the opposite order to the one you want them out in:

pop 4, emit 4, push 6 then 2      stack [6, 2]
pop 2, emit 2, push 3 then 1      stack [6, 3, 1]
pop 1, emit 1                      stack [6, 3]
pop 3, emit 3                      stack [6]
pop 6, ...                         -> 4, 2, 1, 3, 6, ...

Pushing left first would produce node, right, left — a mirror-image traversal that is right on a symmetric test tree and wrong on everything else. It is the one mistake this problem has.

Java

class Solution {
    public List<Integer> preorderTraversal(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);                 // emit on arrival -- nothing to return for

            // A stack reverses, so push RIGHT first to pop left first.
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }

        return out;
    }
}

Null children are filtered before pushing rather than checked after popping, which keeps the stack holding only real nodes — and ArrayDeque rejects nulls anyway, so the alternative would throw.

There is no inner loop, no current pointer and no visited state. Compare that with inorder side by side; the difference is entirely down to when the node is emitted.

Python

class Solution:
    def preorderTraversal(self, root: TreeNode) -> list[int]:
        if root is None:
            return []

        out, stack = [], [root]

        while stack:
            node = stack.pop()
            out.append(node.val)

            if node.right:
                stack.append(node.right)      # right first...
            if node.left:
                stack.append(node.left)       # ...so left comes off first

        return out

A plain list is a fine stack in Python — append and pop are both O(1) at the end. It is only pop(0), the queue operation, that is O(n), which is why level order needs a deque and this does not.

Postorder, and the trick worth knowing

Postorder — left, right, node — is genuinely the awkward one iteratively, because a node must be revisited after both subtrees. There is a shortcut that sidesteps it entirely:

preorder            node, left, right
push LEFT first     node, right, left
reverse that        left, right, node   = POSTORDER

So postorder is this exact loop with the two pushes swapped and the result reversed. Worth knowing: it turns the hardest of the three into the easiest, and if an interviewer asks for postorder iteratively it is the answer to reach for before attempting a genuine two-visit stack.

Complexity

The explicit stack holds at most one node per level plus siblings, so O(h) — the same as the recursion, but on the heap rather than the call stack, which is what saves a degenerate tree from overflowing. Morris threading works for preorder too, with the same tree-mutating caveat as in problem 94.

What the interviewer is checking

• Push right before left, and that you can say why.
• That you can explain why preorder is easier iteratively than inorder.
• Null children filtered on the way in.
• Empty tree and single node.
• That the explicit stack is O(h), same as recursion but on the heap.
• Bonus: postorder as reversed node-right-left.