Tree DFS

Updated Nov 19, 2026 · 4 min read
On this page

    Depth-first search on a tree is recursion: solve the problem for the left subtree, solve it for the right subtree, combine. The hard part is not the traversal but deciding which way information flows. Bottom-up, a node needs its children's answers (height, sum, "is this subtree balanced?"). Top-down, a node needs something from above it (the allowed range in a BST, the path so far). Many problems use both: return one thing upward, and record the real answer on the side.

    Binary Trees covers traversal orders. This page is about the problem-solving shapes.

    When to recognise it

    • Height, depth, diameter, balanced, max path sum: facts about a subtree, so bottom-up.
    • Validate a BST, "path from root with sum X", "good nodes", "max difference with an ancestor": the node needs context from its ancestors, so top-down.
    • Lowest common ancestor: bottom-up. Each call returns "did I find p or q down here?"
    • All root-to-leaf paths: top-down with a shared path list, which is backtracking on a tree (see Backtracking).
    • Serialize, clone, build from traversals: a pre-order walk.

    The two shapes

    Two copies of the tree 3, 9, 20, 15, 7. Left, bottom-up: each node shows the height it returns (1 at the leaves, 2 at 20, 3 at the root). Right, top-down: each node shows the range it receives, such a
    Two copies of the tree 3, 9, 20, 15, 7. Left, bottom-up: each node shows the height it returns (1 at the leaves, 2 at 20, 3 at the root). Right, top-down: each node shows the range it receives, such as (−∞, 3) for 9 and (3, 20) for 15.

    Bottom-up returns a value from each call:

    class TreeNode:
        def __init__(self, val=0, left=None, right=None):
            self.val, self.left, self.right = val, left, right
    
    
    def max_depth(node):
        if not node:
            return 0
        return 1 + max(max_depth(node.left), max_depth(node.right))

    Top-down passes extra parameters:

    def is_bst(node, lo=float('-inf'), hi=float('inf')):
        if not node:
            return True
        if not lo < node.val < hi:
            return False
        return is_bst(node.left, lo, node.val) and is_bst(node.right, node.val, hi)

    Both are O(n) time and O(h) space for the recursion, where h is the height: O(log n) if the tree is balanced, O(n) if it is a chain.

    Return one thing, record another

    Some answers do not flow up cleanly. The diameter (longest path between any two nodes) may bend at a node, using both children, but a path that continues upward can only use one child. So the helper returns a height and records the best bend in an outer variable.

    Tree 1 with children 2 and 3; 2 has children 4 and 5. The path 4, 2, 1, 3 is highlighted. At node 2 the bend is 1 + 1 = 2 edges and it returns height 2; at node 1 the bend is 2 + 1 = 3 edges.
    Tree 1 with children 2 and 3; 2 has children 4 and 5. The path 4, 2, 1, 3 is highlighted. At node 2 the bend is 1 + 1 = 2 edges and it returns height 2; at node 1 the bend is 2 + 1 = 3 edges.
    def diameter(root):
        """Bottom-up with a side answer: return height upward, record the best path through each node."""
        best = 0
        def height(node):
            nonlocal best
            if not node:
                return 0
            l, r = height(node.left), height(node.right)
            best = max(best, l + r)          # path that bends at this node
            return 1 + max(l, r)             # only one branch can continue upward
        height(root)
        return best

    Binary Tree Maximum Path Sum is the same shape with sums instead of heights, plus one twist: a child's contribution is max(0, child), because a negative branch is better left out.

    Top-down with a path

    When you need the actual paths, keep one list, add the node on the way down and remove it on the way back:

    def root_to_leaf_paths(root, target):
        """Top-down with backtracking: the path list is shared, so undo after each child."""
        out, path = [], []
        def go(node, remaining):
            if not node:
                return
            path.append(node.val)
            if not node.left and not node.right and remaining == node.val:
                out.append(path[:])          # copy, the list keeps changing
            go(node.left, remaining - node.val)
            go(node.right, remaining - node.val)
            path.pop()
        go(root, target)
        return out

    Common bugs

    • Validating a BST by comparing a node only with its children. A node deep in the left subtree must also be smaller than the root. Pass (lo, hi) down.
    • Returning the answer instead of the helper value: for diameter or max path sum, the function returns a height (or one-branch sum), not the answer.
    • Appending path instead of path[:]: every saved path ends up as the same, finally empty, list.
    • Forgetting to undo (path.pop()), so paths leak into siblings.
    • Recursion depth on a chain of 10⁵ nodes. Python's default limit is about 1,000. Mention an iterative version with an explicit stack, or sys.setrecursionlimit.

    Say this in the interview

    • "Each call returns the height of its subtree. At every node I also check the path that bends here, left plus right, and keep the best. Every node is visited once: O(n) time, O(h) stack."
    • "For the BST check I pass the allowed range down, because the rule is about all ancestors, not only the parent."

    Problems for this pattern

    1. Maximum Depth of Binary Tree: bottom-up, one line.
    2. Invert Binary Tree: swap children at every node.
    3. Diameter of Binary Tree: return height, record the bend.
    4. Validate Binary Search Tree: top-down ranges.
    5. Lowest Common Ancestor of a Binary Tree: bottom-up "found it" flags.
    6. Kth Smallest Element in a BST: in-order DFS, stop at the k-th node.
    7. Construct Binary Tree from Preorder and Inorder Traversal: pre-order gives the root, in-order splits the subtrees.
    8. Binary Tree Maximum Path Sum: diameter with sums.
    9. Serialize and Deserialize Binary Tree: preorder with null markers, read back in the same order.
    10. Flatten a Nested JSON Object: DFS that carries the key path down.

    Related

    Binary Trees · Binary Search Trees · Tree BFS · Backtracking · Graph BFS and DFS