Recursive DFS Traversal

Most binary tree problems reduce to a single question: can you compute something for the current node using results from the left and right subtrees? If yes, you write a recursive function that trusts its children to return the right answer, combines those answers with information at the current node, and passes the result up to its parent. That is recursive depth-first search on a tree, and it is the single most important technique for tree problems in interviews.

The reason recursion maps so naturally onto trees is that a tree is a recursive data structure. Every node is the root of its own subtree. When you call dfs(node.left), you are solving the exact same problem on a smaller tree. The recursion bottoms out at null nodes, where you return some base value, and then results bubble back up through the call stack, assembling the final answer.

The three traversal orders

When you visit every node in a tree recursively, the order in which you process the current node relative to its children gives rise to three classic traversal orders.

Preorder (root, left, right) processes the current node before its children. This is useful when you need to pass information downward, for example, building a path from root to leaf, or serializing a tree.

Inorder (left, root, right) processes the left subtree first, then the current node, then the right subtree. On a binary search tree, inorder traversal visits nodes in sorted order. This makes it the go-to approach for problems like finding the kth smallest element or implementing an iterator.

Postorder (left, right, root) processes both children before the current node. This is the order you need when the answer at a node depends on answers from its children: computing heights, counting nodes, or checking balance. Most "compute a property of the tree" problems are naturally postorder.

In practice, many problems blend these orders. You might pass bounds downward (preorder flavor) while also returning a boolean upward (postorder flavor). The labels are less important than the underlying question: does this node need information from above, from below, or both?

Max depth: the simplest recursive DFS

LeetCode 104 asks for the maximum depth of a binary tree, the number of nodes along the longest path from the root down to the farthest leaf. This is the "hello world" of recursive tree problems.

The recursive insight is immediate: the max depth of a tree is 1 (for the current node) plus the maximum of the depths of its left and right subtrees. A null node has depth 0.

Let's trace through a small example:

        3
       / \
      9   20
         /  \
        15   7

We call max_depth(3). This calls max_depth(9) and max_depth(20). The call max_depth(9) has two null children, so both return 0, and max_depth(9) returns 1 + max(0, 0) = 1. The call max_depth(20) recurses to max_depth(15) and max_depth(7), both of which return 1 (same reasoning as node 9). So max_depth(20) returns 1 + max(1, 1) = 2. Back at the root, max_depth(3) returns 1 + max(1, 2) = 3.

The code is almost a direct translation of the English description:

def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

Three lines. That is the power of recursive DFS: when the problem decomposes cleanly, the code is trivially short.

Validate BST: passing bounds downward

Consider LeetCode 98: a binary search tree has the property that for every node, all values in its left subtree are strictly less than the node's value, and all values in its right subtree are strictly greater. A common mistake is to only check that each node's value is greater than its left child and less than its right child. That check is local and misses cases where a deeper node violates the BST property with respect to an ancestor.

The correct approach is to pass a valid range downward. The root can hold any value, so it starts with the range (-infinity, +infinity). When you go left, the current node's value becomes the new upper bound. When you go right, the current node's value becomes the new lower bound. At every node, you check whether the node's value falls within its inherited range.

Why does this work? Because each node inherits a valid range from all of its ancestors, not just its parent. When you descend left from a node with value 10, you set hi = 10. If you then descend right from that child (say it has value 5), you set lo = 5. Now the grandchild must satisfy 5 < val < 10, which correctly encodes both the parent and grandparent constraints. The bounds accumulate the full ancestry.

def is_valid_bst(root, lo=float('-inf'), hi=float('inf')):
    if not root:
        return True
    if root.val <= lo or root.val >= hi:
        return False
    return (is_valid_bst(root.left, lo, root.val) and
            is_valid_bst(root.right, root.val, hi))

This is a preorder-style traversal: you check the current node's validity before recursing into children. The bounds flow downward through the recursion, and a boolean result flows upward. If any node fails the check, the and short-circuits and the whole tree is invalid.

Same tree and symmetric tree: comparing two subtrees simultaneously

Some tree problems ask you to compare two subtrees at the same time. LeetCode 100, "Same tree," checks whether two trees are structurally identical with the same values. Its companion, LeetCode 101, "Symmetric tree," checks whether a single tree is a mirror image of itself.

For same tree, you recurse on both trees in lockstep. Two nodes are the same if they are both null, or if they have the same value and their left children are the same and their right children are the same.

def is_same_tree(p, q):
    if not p and not q:
        return True
    if not p or not q:
        return False
    return (p.val == q.val and
            is_same_tree(p.left, q.left) and
            is_same_tree(p.right, q.right))

Symmetric tree is almost the same problem, but mirrored. A tree is symmetric if its left subtree is a mirror of its right subtree. Two subtrees are mirrors if their roots have the same value, the left child of one mirrors the right child of the other, and vice versa.

def is_symmetric(root):
    def is_mirror(a, b):
        if not a and not b:
            return True
        if not a or not b:
            return False
        return (a.val == b.val and
                is_mirror(a.left, b.right) and
                is_mirror(a.right, b.left))
    return is_mirror(root.left, root.right) if root else True

The only difference from same tree is swapping which children you compare. These two problems illustrate how a tiny change in the recursive structure encodes a fundamentally different question.

The general pattern

Whenever you face a binary tree problem, ask yourself two questions. First: what information do I need from my children to compute the answer at this node? That determines the return type of your recursive function. For max depth, children return an integer (their depth). For validate BST, children return a boolean (whether the subtree is valid). For more complex problems, children might return a tuple, for example, (is_balanced, height) when checking whether a tree is balanced.

Second: what information do I need to pass down from above? For max depth, nothing. For validate BST, you pass bounds. For path sum problems, you pass the running sum.

Once you answer these two questions, the code writes itself: define the base case, recurse on children, combine results, and return.

Inorder traversal and BST sorted order

A binary search tree has a special relationship with inorder traversal: visiting nodes in left-root-right order yields the values in sorted (ascending) order. This property is the basis for several interview problems.

For LeetCode 230, finding the kth smallest element in a BST, perform an inorder traversal and return the kth value you encounter. You can do this with a simple counter:

def kth_smallest(root, k):
    count = 0
    result = None

    def inorder(node):
        nonlocal count, result
        if not node or result is not None:
            return
        inorder(node.left)
        count += 1
        if count == k:
            result = node.val
            return
        inorder(node.right)

    inorder(root)
    return result

The same idea powers a BST iterator: maintain a stack of nodes representing the "pending" inorder traversal. Each call to next() advances the traversal by one step.

Iterative DFS with an explicit stack

Recursive DFS uses the call stack implicitly. For very deep trees, particularly skewed ones with $O(n)$ height, this can cause a stack overflow. The alternative is to manage your own stack explicitly.

The iterative version of preorder traversal is straightforward. Push the root onto a stack. While the stack is not empty, pop a node, process it, then push its right child followed by its left child (right first so that left is processed first).

def preorder_iterative(root):
    if not root:
        return []
    result = []
    stack = [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

Iterative inorder is slightly trickier. You need to push all the left descendants of the current node before processing anything, then process the node, then move to its right child:

def inorder_iterative(root):
    result = []
    stack = []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result

In interviews, the recursive version is almost always preferred for clarity. Use iterative DFS only when explicitly asked, when the tree might be extremely deep, or when the problem naturally fits a stack-based approach (like the BST iterator).

Complexity analysis

Time complexity: $O(n)$. Every node is visited exactly once. Whether you use preorder, inorder, or postorder, the total work is proportional to the number of nodes.

Space complexity: $O(h)$, where h is the height of the tree. This is the maximum depth of the recursion stack (or the explicit stack in the iterative version). For a balanced tree, h = $O(\log n)$. For a completely skewed tree (essentially a linked list), h = $O(n)$. This is the worst case you should mention in interviews.

The space is used regardless of whether you recurse or iterate. The explicit stack in the iterative version uses the same $O(h)$ memory. The difference is that the explicit stack lives on the heap rather than the call stack, which can handle larger sizes and avoids stack overflow errors.

Recognizing this pattern

You're probably looking at recursive DFS on a tree when:

• The problem asks you to compute a single property (height, count, boolean, sum) over an entire tree where the value at each node depends on its subtrees.
• Subtree-local information bubbles up cleanly, so you can describe the answer at a node purely as a combination of the left and right return values plus the node itself.
• The recursion shape is the tree itself, not a DP over (node, state) pairs with overlapping subproblems.
• Information either flows down as arguments (bounds, paths) or up as return values, but you do not need explicit memoization keyed on multiple dimensions.

Common templates:

• Postorder gather: return a value computed from dfs(left) and dfs(right). Example: Maximum Depth of Binary Tree.
• Preorder bounds pass-down: push a constraint downward and short-circuit on violation. Example: Validate Binary Search Tree.
• Parallel lockstep recursion: recurse on two trees simultaneously and combine. Example: Same Tree.
• Inorder with counter: exploit BST sorted-order property during a left-root-right walk. Example: Kth Smallest Element in a BST.