Tree depth-first search

Problem

A tree gives you a root and, at each node, a left and a right child that may be missing. There is no index and no way to jump to a node. You reach everything by walking down from the root. Depth-first search walks one branch to its end before trying the next, which is exactly what a recursive function on a node does. The questions are about the whole shape: how deep is it, is it balanced, are these two trees equal, what is the best path, who is the common ancestor of two nodes.

Intuition

Imagine you are a manager of a team tree and you want the headcount. You do not count everyone yourself. You ask your two direct reports, "how many people are under you?", each of whom asks theirs, and you answer their numbers added together, plus one for me. Someone with no reports answers zero immediately. You never need to know how the work gets done below you; you only trust the contract that each report returns the correct answer for their own team. That trust is the entire technique, and the proof that it works is the same as for any recursion: if the answer is right for the smallest trees and the combine step is right whenever the children's answers are right, then it is right for every tree.

The only real decision is when to do your own work. Do it before asking the children and you can pass what you know down to them (preorder). Do it between the two questions and, in a search tree, you meet the values in sorted order (inorder). Do it after both answers arrive and you can use what the children found (postorder). Pick the order by asking which direction the information needs to travel.

Same tree three times; the number in a circle is when that node is visited. Preorder starts at the top, inorder starts at the leftmost node, and postorder ends at the root. The filled node is the first one visited.

Mechanics

The contract and the base case

Write down, in one sentence, what f(node) returns for the whole subtree at node, including node = None. The recursion is then forced: handle the empty tree, call f on both children, combine. Correctness is induction on subtree size: f(None) is right by the base case, and if f is right for both children then the combine step makes it right for the node. Bugs come from a vague contract: the height of an empty tree is 0 here, not −1, and mixing the two conventions between base case and combine is the most common error.

Information flowing down, information flowing up

Down is a parameter: the sum so far, the maximum on the path from the root, the remaining target. It describes the path from the root to this node, which only the ancestors know. Up is a return value: height, size, whether a target was found, the best total below. It describes the subtree, which only the descendants know. A problem that needs both passes them in both directions at once; counting good nodes only passes down, balance checking only returns up, and path sum with a target uses both.

Return one thing, record another

The trickiest family is where the best answer is a path that is allowed to bend at its highest node. A parent can extend a path that goes down through exactly one child, so that is what a node must return. But the best path overall may use both children at some node, so each node also computes the bent path and updates a running best. For the diameter, a node returns its height but records left + right; for the maximum path sum, a node returns its value plus the better child's gain (never less than zero) but records its value plus both gains. The two numbers answer different questions: one is for the caller, one is for the final result.

Iterative versions

Recursion uses the call stack, so each order can also use an explicit stack. Preorder pushes the root, then pops a node, visits it, and pushes its right child before its left (so the left comes off first). Inorder goes left as far as it can pushing nodes, then pops, visits and turns right. Postorder is easiest as preorder with the children swapped (root, right, left) and the result reversed. The need arises because Python's default recursion limit is about 1000 frames: a degenerate tree shaped like a list with 10⁵ nodes overflows it even though the algorithm is correct.

Each node shows the height it returns (h) and the longest path bending there (bend, in edges). The amber node has the largest bend: that value is the tree's diameter.

Worked example

The three orders. For the tree in the diagrams (root 5):

The inorder list is increasing because this tree is a search tree: everything in a left subtree is smaller than its root and everything in the right is larger.

Height and diameter. Postorder, so every node is processed after its children:

The root returns 4, so the tree has depth 4. The largest bend is 5 edges, at node 5, so the diameter is 5.

Maximum path sum. A different tree, with a negative value in the middle: root 6, a left child -3 with children 5 and 2, and a right child 4 whose left child is -1. Each node clamps a negative child gain to zero:

The best bent path sum is 12. Node -3 returns only 2, since a parent can extend just one side, but the root can still use that side together with its right side.

Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


def preorder(root):
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right:
            stack.append(node.right)                 # right first so left pops first
        if node.left:
            stack.append(node.left)
    return out


def inorder(root):
    out, stack, cur = [], [], root
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        out.append(cur.val)
        cur = cur.right
    return out


def postorder(root):
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return out[::-1]                                 # root, right, left reversed


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


def diameter(root):
    best = 0

    def height(node):
        nonlocal best
        if not node:
            return 0
        left, right = height(node.left), height(node.right)
        best = max(best, left + right)               # record the bend
        return 1 + max(left, right)                  # return the straight part

    height(root)
    return best


def is_balanced(root):
    def height(node):
        if not node:
            return 0
        left = height(node.left)
        if left == -1:
            return -1
        right = height(node.right)
        if right == -1 or abs(left - right) > 1:
            return -1                                # sentinel for unbalanced
        return 1 + max(left, right)

    return height(root) != -1


def is_same(a, b):
    if not a or not b:
        return a is b
    return a.val == b.val and is_same(a.left, b.left) and is_same(a.right, b.right)


def is_subtree(root, sub):
    return bool(root) and (is_same(root, sub) or is_subtree(root.left, sub) or is_subtree(root.right, sub))


def is_symmetric(root):
    def mirror(a, b):
        if not a or not b:
            return a is b
        return a.val == b.val and mirror(a.left, b.right) and mirror(a.right, b.left)

    return not root or mirror(root.left, root.right)


def count_good(root):
    def go(node, top):
        if not node:
            return 0
        return (node.val >= top) + go(node.left, max(top, node.val)) + go(node.right, max(top, node.val))

    return go(root, float("-inf"))


def lowest_common_ancestor(root, p, q):
    if root is None or root is p or root is q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    return root if left and right else left or right


def max_path_sum(root):
    best = float("-inf")

    def gain(node):
        nonlocal best
        if not node:
            return 0
        left, right = max(0, gain(node.left)), max(0, gain(node.right))
        best = max(best, node.val + left + right)
        return node.val + max(left, right)

    gain(root)
    return best


def path_sum_paths(root, target):
    paths, path = [], []

    def go(node, remaining):
        if not node:
            return
        path.append(node.val)
        remaining -= node.val
        if not node.left and not node.right and remaining == 0:
            paths.append(path[:])
        go(node.left, remaining)
        go(node.right, remaining)
        path.pop()                                   # undo on the way back

    go(root, target)
    return paths


def rob_tree(root):
    def go(node):
        if not node:
            return 0, 0
        take_l, skip_l = go(node.left)
        take_r, skip_r = go(node.right)
        return node.val + skip_l + skip_r, max(take_l, skip_l) + max(take_r, skip_r)

    return max(go(root))


def delete_leaves(root, target):
    if not root:
        return None
    root.left = delete_leaves(root.left, target)
    root.right = delete_leaves(root.right, target)
    if not root.left and not root.right and root.val == target:
        return None
    return root

is_same and mirror use a is b after the guard: if either node is missing, the trees agree only when both are missing. is_subtree assumes sub is not empty; an empty tree is trivially a subtree of anything, so handle that before the call.

Variations and edge cases

• Pass the path down, record at the leaf. Path sums and root-to-leaf listings append to a shared list before recursing and pop afterwards. Copy the list (path[:]) when recording, or every stored path will be emptied by the later pops.
• Return a pair. House robber on a tree returns (best with this node taken, best with it skipped). Any problem where the parent's choice depends on the child's choice returns one value per state.
• Return a sentinel. Balance checking uses −1 for "already failed", which avoids a second pass that would recompute heights repeatedly (that version is O(n²) on a skewed tree).
• Rebuild on return. Pruning, inverting and deleting reassign root.left and root.right from the recursive calls and return the node (or None to remove it).
• Edge cases: an empty tree, a single node, a chain of nodes that is deeper than the recursion limit, negative values (the clamp to zero in the path sum), duplicate values (compare nodes with is when the problem gives you the node, not its value), and trees where a leaf is a node with both children missing, not merely one.

Complexity and tradeoffs

• Time: O(n). Each node is visited once and does constant work besides the calls. The height trace above took 7 steps for 7 nodes. Checking whether one tree is a subtree of another is O(n·m) in the worst case, since is_same may run at every node.
• Space: O(h), where h is the tree's height, for the call stack or the explicit stack: about log n for a balanced tree and n for a chain. Paths that are stored add the size of the output.
• Baseline. Computing height separately at every node, as in a naive balance check, repeats work and costs O(n²) on a skewed tree. Returning the height from the same pass makes it O(n).
• When it fails. Questions about distance from the root, level by level, or the nearest node to something are shortest-path questions on a tree and are cleaner with breadth-first search. Questions about a graph that may contain cycles need a visited set. And when the input is a search tree, use its order to skip half the tree (see the binary search trees page) instead of visiting every node.

Problems

The home problems fall into four groups: the traversals themselves (preorder, inorder, postorder); questions about shape computed by returning values up (depth, balance, diameter, maximum path sum, house robber III, deleting leaves); comparing trees (same, symmetric, subtree, invert); and carrying state down (good nodes, path sum II, lowest common ancestor). Serialization, search-tree validation, right-side view and the like have another home page and are listed below as "also uses".

Easy

• 94. Binary Tree Inorder Traversal NeetCode 250
  Go left as far as possible pushing nodes, then pop, visit and turn right; this explicit stack mirrors the recursion.
• 100. Same Tree Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Two trees match when their roots match and both pairs of subtrees match recursively, with two empty nodes counting as equal.
• 101. Symmetric Tree Grind 169
  Compare the tree with its own mirror image: left's left against right's right, and left's right against right's left.
• 104. Maximum Depth of Binary Tree Blind 75 Grind 169 NeetCode 150 NeetCode 250
  A tree's depth is one more than the deeper of its two subtrees, with an empty tree having depth zero.
• 110. Balanced Binary Tree Grind 169 NeetCode 150 NeetCode 250
  Return each subtree's height upward, with a sentinel for unbalanced, so the whole check is one postorder pass.
• 144. Binary Tree Preorder Traversal NeetCode 250
  Visit a node, then push its right child before its left, so the left subtree comes off the stack first.
• 145. Binary Tree Postorder Traversal NeetCode 250
  Children must be finished before their parent, which an iterative version handles with a last-visited pointer or a reversed root-right-left order.
• 226. Invert Binary Tree Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Swap every node's left and right children, in any traversal order.
• 543. Diameter of Binary Tree Grind 169 NeetCode 150 NeetCode 250
  The longest path through a node is its left height plus its right height, so track the best of those while returning heights.
• 572. Subtree of Another Tree Blind 75 Grind 169 NeetCode 150 NeetCode 250
  At every node of the larger tree, check whether the subtree rooted there is the same tree as the smaller one.

Medium

• 113. Path Sum II Grind 169
  Carry the remaining sum and the current path downward, record the path at a leaf that hits zero, and pop on the way back.
• 236. Lowest Common Ancestor of a Binary Tree Grind 169
  Each subtree returns p or q if it holds one, and the answer is the first node that gets a hit from both sides, or p or q itself when the other lies below it.
• 337. House Robber III NeetCode 250
  Each node returns two values, its best total if robbed and if skipped, and its parent combines them.
• 1325. Delete Leaves With a Given Value NeetCode 250
  Process children before their parent, so a parent whose children were removed can itself be removed as a leaf.
• 1448. Count Good Nodes in Binary Tree NeetCode 150 NeetCode 250
  Carry the largest value on the path from the root down; a node is good when it is at least that value.

Hard

• 124. Binary Tree Maximum Path Sum Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Each node returns the best downward path it can extend upward, while the answer also considers bending through the node with both children.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 98. Validate Binary Search Tree Medium
• 199. Binary Tree Right Side View Medium
• 211. Design Add and Search Words Data Structure Medium
• 230. Kth Smallest Element in a BST Medium
• 437. Path Sum III Medium
• 863. All Nodes Distance K in Binary Tree Medium
• 297. Serialize and Deserialize Binary Tree Hard

Connections

This page applies the recursion page's habits to a branching structure, and the explicit-stack versions come from the stack page. Breadth-first search is the other way to traverse a tree and answers level-based questions. When the tree is ordered, the binary search trees page uses the same traversals with extra pruning; and the "carry a running value down, update a best on the way" shape reappears in Kadane's algorithm and in prefix sums on paths.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, section 10.4 (representing rooted trees) and section 12.1 (inorder walks of a search tree); the depth-first search of chapter 22 is the graph generalisation.
• Sedgewick and Wayne, Algorithms, section 3.2: binary search trees and their traversals.
• Skiena, The Algorithm Design Manual: the treatment of traversal orders and recursion on trees.
• Knuth, The Art of Computer Programming, volume 1, section 2.3.1: traversing binary trees, which names and compares the three orders.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.