Tree traversal

Binary tree traversal for coding interviews. Depth-first recursion that returns values up or passes ranges down, breadth-first level order, a step-through of max depth, code in Java, Python, C#, Go and TypeScript, and 10 LeetCode problems.

Foundation13 min read

Tree problems scare people because recursion feels like magic. It stops feeling that way once you see that almost every tree problem is one of two questions:

What does each subtree hand back to its parent? Its height, its sum, whether it’s balanced, whether it contains a target. Information flows up.
What does each node need to know from above? The range its value must fall in, the path so far, its depth. Information flows down.

Answer that question, write the empty-tree case, and the recursion writes itself. The third tool is breadth-first traversal with a queue, for anything that talks about levels.

How to spot it

Any problem on a binary tree, so the question is really which traversal:

Depth, height, balance, diameter, path sums, lowest common ancestor: bottom-up DFS.
Validating a BST, root-to-leaf paths, “good nodes”: top-down DFS, carrying state down.
Level order, right side view, zigzag, minimum depth, anything “per level”: BFS.
Sorted order from a BST, kth smallest: in-order DFS (left, node, right), which visits a BST’s values in increasing order.

Watch it run

Max depth, bottom-up. Each call waits for both children. So the deepest nodes answer first, and the answers flow back up. The yellow nodes are on the call stack, still waiting. Green ones have returned, with the value they handed back underneath.

call stack bottom → top

empty

def depth(node):
if node is None: return 0
left_depth = depth(node.left)
right_depth = depth(node.right)
return 1 + max(left_depth, right_depth) # combine

How deep is this tree? Ask each subtree, and combine the answers on the way back up.

1 / 16

The stack never holds more than the height of the tree: here 4 calls, for 7 nodes. On a balanced tree of a million nodes that’s about 20. On a tree that is one long chain, it’s a million, which is why the recursion limit comes up in interviews.

The template

Bottom-up depth, top-down BST validation, and BFS level order:

TreeTraversal.javanode.pyTreeTraversal.csnode.gotree-node.ts

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class TreeTraversal {
    record Node(int val, Node left, Node right) {
        Node(int val) {
            this(val, null, null);
        }
    }

    static int maxDepth(Node node) {
        // Bottom-up: each subtree hands back one number, and the parent combines them. Write
        // the empty-tree case first, then trust the recursive calls.
        if (node == null) return 0;
        return 1 + Math.max(maxDepth(node.left()), maxDepth(node.right()));
    }

    static boolean isBst(Node node, long low, long high) {
        // Top-down: the parent passes down the range every value below it must fall in.
        // Checking only left.val < val misses a grandchild on the wrong side of the root.
        // long bounds, so a node holding Integer.MAX_VALUE still fits strictly inside.
        if (node == null) return true;
        if (node.val() <= low || node.val() >= high) return false;
        return isBst(node.left(), low, node.val()) && isBst(node.right(), node.val(), high);
    }

    static List<List<Integer>> levelOrder(Node root) {
        // Breadth-first: a queue visits nodes in order of depth. Reading the size before the
        // inner loop tells us exactly how many nodes make up the current level.
        List<List<Integer>> levels = new ArrayList<>();
        Queue<Node> queue = new ArrayDeque<>();
        if (root != null) queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            for (int remaining = queue.size(); remaining > 0; remaining--) {
                Node 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;
    }

    public static void main(String[] args) {
        //        1
        //      2   3
        //     4 5    6
        //       7
        Node tree = new Node(1, new Node(2, new Node(4), new Node(5, new Node(7), null)),
                new Node(3, null, new Node(6)));
        check(maxDepth(tree) == 4);
        check(maxDepth(null) == 0);
        check(levelOrder(tree).equals(List.of(List.of(1), List.of(2, 3), List.of(4, 5, 6), List.of(7))));
        check(isBst(new Node(5, new Node(3, new Node(1), new Node(4)), new Node(8)), Long.MIN_VALUE, Long.MAX_VALUE));
        check(!isBst(new Node(5, new Node(3, null, new Node(6)), new Node(8)), Long.MIN_VALUE, Long.MAX_VALUE));
        System.out.println("ok: maxDepth, isBst and levelOrder");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError();
    }
}

Three habits keep tree recursion correct:

Write the None case first. It’s almost always return 0, return True or return None, and it stops the recursion.
Trust the recursive call. Assume max_depth(node.left) returns the right answer for the left subtree. Don’t trace it in your head. Only check that you combine correctly.
Decide what flows which way before you code. Bounds go down as parameters. Heights come up as return values.

Returning one thing, recording another

Diameter of a binary tree is the longest path between any two nodes. The longest path through a node is height(left) + height(right), but the parent needs that node’s height, not its diameter. So the function returns the height and updates a best variable with left + right along the way. Binary tree maximum path sum is the same shape with sums: return the best one-sided path, and record the best two-sided one.

In-order for BSTs

An in-order traversal of a BST visits values in sorted order. Kth smallest is “stop at the kth visit”. Validate BST also has an in-order solution: check that each visited value is bigger than the previous one. It’s a nice alternative to passing bounds, and worth mentioning.

Lowest common ancestor

Return the node if it’s one of the two targets, otherwise recurse both ways. If both sides return something, the current node is where the paths split: it’s the answer. If only one side does, pass that result up. Each node is visited once, so it’s O(n).

Complexity

	Time	Extra memory
Any DFS	O(n)	O(h): about log n if balanced, n if it’s a chain
BFS	O(n)	O(w), the widest level: up to about n/2

Say this out loud

Each subtree can report its height, and a node’s height is one more than its taller child, so I’ll recurse bottom-up. Every node is visited once: O(n) time, and O(h) stack.

Interview questions

Interviewer asksWhat happens if the tree is a long chain of a million nodes?

Recursive DFS goes a million calls deep, and overflows the stack. Python’s default limit is 1,000 calls. Java and C# stacks typically hold tens of thousands of frames. Fix it with an explicit stack (iterative DFS), or with BFS. Go’s stacks grow on demand, so it survives longer. But memory is still O(n).

Interviewer asksMinimum depth: why is BFS better than DFS here?

BFS visits levels in order, so the first leaf it reaches is at the minimum depth and it can stop there. DFS has to explore the whole tree to be sure. On a tree with a shallow leaf and a huge deep subtree, BFS does far less work.

Interviewer asksSerialize and deserialize a binary tree: which traversal would you use?

Use pre-order (node, left, right), with a marker for empty children, such as 1,2,#,#,3,#,#. Pre-order puts each root before its subtrees. So deserializing is the same recursion in reverse. Read a value, and build the node. Then build its left and right subtrees from what follows. The markers are what make the tree unambiguous.

Practice

10 problems on LeetCode: 4 easy, 5 medium, 1 hard

Ticks are saved in this browser only. Clear your site data and they're gone.

Recap

Ask first: what flows up (return values) and what flows down (parameters)?
DFS: None case, recurse, combine. BFS: queue, one level at a time.
In-order on a BST gives sorted order.
When the answer isn’t the return value, return what the parent needs and record the answer on the side.
Cost: O(n) time. O(h) memory for DFS, and O(width) for BFS. Deep chains overflow recursion.