templates · Trees

Tree traversals (pre, in, post — recursive and iterative)

  • "Return the preorder / inorder / postorder" of a binary tree
  • A BST in sorted order: inorder visits the values smallest first
  • The interviewer says "now without recursion", or the tree can be very deep (a skewed tree)

Iterative tree DFS (explicit stack)

the one rule

The invariant

The stack holds exactly the nodes we have reached but not finished yet; the top is the one to handle next.

write it from memory

The template

recursive: one skeleton, three orders

javajava.util.*
/** order: 0 = preorder, 1 = inorder, 2 = postorder. Only the position of the visit line changes. */static void walk(TreeNode node, int order, List<Integer> out) {    if (node == null) return;    if (order == 0) out.add(node.val);                 // pre: node, left, right    walk(node.left, order, out);    if (order == 1) out.add(node.val);                 // in: left, node, right    walk(node.right, order, out);    if (order == 2) out.add(node.val);                 // post: left, right, node}

The three orders differ only in where the visit line sits: before, between or after the two calls.

fill in the blanks — only these lines change per problem

  1. line 3The base case. Most problems return a value here (0, true, null) instead of nothing.

iterative preorder

javajava.util.*
static List<Integer> preorder(TreeNode root) {    List<Integer> out = new ArrayList<>();    Deque<TreeNode> stack = new ArrayDeque<>();    if (root != null) stack.push(root);    while (!stack.isEmpty()) {        TreeNode node = stack.pop();        out.add(node.val);                             // visit as soon as it is popped        if (node.right != null) stack.push(node.right); // right first, so left is popped first        if (node.left != null) stack.push(node.left);    }    return out;}

fill in the blanks — only these lines change per problem

  1. line 8Push order. Right first, then left, so that left comes out first.

iterative inorder

javajava.util.*
static List<Integer> inorder(TreeNode root) {    List<Integer> out = new ArrayList<>();    Deque<TreeNode> stack = new ArrayDeque<>();        // the path we must come back to    TreeNode cur = root;    while (cur != null || !stack.isEmpty()) {        while (cur != null) {                          // dive left as far as possible            stack.push(cur);            cur = cur.left;        }        cur = stack.pop();                             // nothing unvisited on its left        out.add(cur.val);                              // visit (stop early here for "k-th smallest")        cur = cur.right;                               // then its right subtree    }    return out;}

Dive left, pop, visit, go right. This is the one to know by heart: it also powers the BST iterator.

fill in the blanks — only these lines change per problem

  1. line 11What "visit" means: add to a list, count to k and return, or compare with the previous value (validate BST).

iterative postorder

javajava.util.*
static List<Integer> postorder(TreeNode root) {    List<Integer> out = new ArrayList<>();    Deque<TreeNode> stack = new ArrayDeque<>();    TreeNode cur = root, lastDone = null;              // lastDone = the node we finished just before    while (cur != null || !stack.isEmpty()) {        while (cur != null) {            stack.push(cur);            cur = cur.left;        }        TreeNode top = stack.peek();        if (top.right != null && top.right != lastDone) { // right side not done yet: go there            cur = top.right;        } else {            stack.pop();            out.add(top.val);                          // both children done: visit            lastDone = top;        }    }    return out;}

Visit a node only when its right side is done. lastDone tells you if you just came back from the right child.

fill in the blanks — only these lines change per problem

  1. line 11When to go right instead of visiting: there is a right child and we did not just finish it.

complexity

What it costs

time O(n)
Every node is pushed once and popped once (postorder may peek at it twice). That is a constant amount of work per node.
space O(h)
The stack (or the call stack) holds at most one path from the root, h = the height: about log₂ n for a balanced tree, n for a skewed one.

watch out

Common bugs

  • Pushing left before right in iterative preorder. The output comes out mirrored.
  • Inorder loop guard while (!stack.isEmpty()) alone. It stops before the first push; use cur != null || !stack.isEmpty().
  • Using Stack<TreeNode>. It is an old synchronized class; use ArrayDeque with push/pop/peek.

use it

Practise it on

learn it properly