Tree Traversal (DFS & BFS)

Tree Traversal (DFS & BFS)

To do anything with a tree (search it, copy it, measure it, print it), you have to visit its nodes in some order. There are two families of orders:

• Depth-first (DFS): go as deep as possible down one branch before backing up. Depending on when you process the current node relative to its children, you get preorder, inorder or postorder.
• Breadth-first (BFS): visit the tree level by level, top to bottom. This is also called level order.

Choosing the right order is often most of the solution. "Process a node before its children" (copying, serializing), "after its children" (heights, deleting, anything that needs the children's answers first), "in sorted order" (BSTs) and "by depth" (right-side view, minimum depth) each map to one traversal.

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

For the example tree below, the three DFS orders are:

        4
      /   \
     2     6          preorder  (root, left, right): 4 2 1 3 6 5 7
    / \   / \         inorder   (left, root, right): 1 2 3 4 5 6 7   ← sorted, because it's a BST
   1   3 5   7        postorder (left, right, root): 1 3 2 5 7 6 4
                      level order:                   4 | 2 6 | 1 3 5 7

Recursive DFS: the shape of most tree solutions

void inorder(TreeNode node, List<Integer> out) {
    if (node == null) return;          // base case: empty subtree
    inorder(node.left, out);
    out.add(node.val);                 // move this line up for preorder, down for postorder
    inorder(node.right, out);
}

The more important skill is using recursion to return information upwards. Decide what each call returns for its subtree, and combine the children's answers:

int height(TreeNode node) {                       // postorder: needs both children first
    if (node == null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}

boolean isSymmetric(TreeNode a, TreeNode b) {     // compare two subtrees in mirrored order
    if (a == null || b == null) return a == b;
    return a.val == b.val && isSymmetric(a.left, b.right) && isSymmetric(a.right, b.left);
}

Recursion uses the call stack: O(h) space, where h is the height. That's O(log n) for a balanced tree, but O(n) for a degenerate, list-shaped tree, which can overflow the stack in Java for trees tens of thousands deep. That's the main reason to know iterative versions.

Iterative DFS with an explicit stack

Preorder: pop a node, record it, push the right child then the left (the stack is last-in-first-out, so left is processed first):

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);
        if (node.right != null) stack.push(node.right);
        if (node.left != null)  stack.push(node.left);
    }
    return out;
}

Inorder: walk left as far as possible, pushing nodes. Pop one, record it, then move to its right subtree:

List<Integer> inorder(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) { stack.push(cur); cur = cur.left; }   // dive left
        cur = stack.pop();
        out.add(cur.val);
        cur = cur.right;                                            // then the right subtree
    }
    return out;
}

This one is worth memorizing. It's the core of the BST iterator (return the next smallest element on demand) and k-th smallest in a BST (stop after k pops).

Postorder: the simplest trick is a modified preorder (root, right, left), reversed at the end:

List<Integer> postorder(TreeNode root) {
    LinkedList<Integer> out = new LinkedList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    if (root != null) stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        out.addFirst(node.val);                      // prepend = reverse at the end
        if (node.left != null)  stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return out;
}

BFS: level order with a queue

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> levels = new ArrayList<>();
    Queue<TreeNode> queue = new ArrayDeque<>();
    if (root != null) queue.add(root);
    while (!queue.isEmpty()) {
        int size = queue.size();                     // exactly the nodes of the current level
        List<Integer> level = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null)  queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        levels.add(level);
    }
    return levels;
}

Taking queue.size() before the inner loop is what separates the levels. Children added during the loop belong to the next level. Many problems are small edits to this template:

• Right side view: the last node of each level.
• Level averages or maximums: aggregate level instead of storing it.
• Zigzag order: alternate between appending and prepending within each level.
• Minimum depth: return the level number at the first leaf reached. BFS finds it without exploring deeper branches.
• Connect next-right pointers: link each node to the next in the same level.

BFS memory is O(w), the maximum width of the tree, which can be about n/2 at the bottom level of a full tree.

Choosing a traversal

Morris traversal: O(1) extra space (bonus)

Morris inorder traversal temporarily points each predecessor's empty right link back to the current node, so it can climb back up without a stack, then removes those links. It's O(n) time and O(1) extra space. It's rarely required, but it's a strong answer when an interviewer asks "can you do it without a stack or recursion?".

Follow-up questions this topic invites — and their answers

Q: Why does inorder traversal of a BST give sorted output? A: In a BST, everything in the left subtree is smaller than the node and everything in the right subtree is larger. Inorder visits left subtree, node, right subtree, and applying that recursively produces the values in ascending order.

Q: What's the space complexity of recursive DFS? A: O(h) for the call stack, where h is the tree's height: O(log n) if balanced, O(n) in the worst case (a skewed tree). Very deep trees can cause StackOverflowError in Java, so iterative traversal is safer for untrusted inputs.

Q: Can you rebuild a tree from its traversals? A: Preorder + inorder (or postorder + inorder) uniquely determine a binary tree with distinct values: preorder gives the root, and its position in the inorder sequence splits the left and right subtrees. Preorder + postorder alone isn't enough in general. For serialization, record null children explicitly, and then preorder alone is enough.

Q: DFS or BFS for "minimum depth of a binary tree"? A: BFS, because it stops at the first leaf it meets, which is by definition the shallowest. DFS must explore every path to be sure. Watch out for the classic bug: a node with only one child is not a leaf, so min(left, right) over a null child gives a wrong answer of 1.

Q: How do you do an iterative inorder traversal? A: Push nodes while going left. When you can't go further, pop a node, visit it, then continue from its right child, repeating until both the current pointer is null and the stack is empty.