Recursion on trees (height, diameter, LCA)

A tree is recursive by nature: each child is the root of a smaller tree. So a function on a tree usually handles the empty tree as a base case, calls itself on the left and right children, and combines the two results. If you trust that the calls return correct answers for the subtrees, you only have to reason about one node.

Three classic examples show the idea. Height (maximum depth): 1 plus the larger child height. Diameter: the longest path between any two nodes, which at its highest point bends through some node, so it equals left height plus right height at that node. Lowest common ancestor (LCA): the deepest node that has both target nodes in its subtree.

Information can flow down (pass depth, a running sum, or bounds as arguments, called top-down) or up (return heights, sizes or flags, called bottom-up). Many hard problems combine both, or track a global best while returning something different to the parent.

1. 1Define the function precisely, for example: height(node) returns the number of nodes on the longest path from node down to a leaf, and 0 for an empty node.
2. 2Write the base case for the empty node (and sometimes for a leaf).
3. 3Recurse on both children and trust the results.
4. 4Combine: height is 1 + max(left, right). For diameter, also update a global best with left + right, the longest path that bends at this node.
5. 5For LCA in a binary tree: if the node is empty or equals p or q, return it. Otherwise recurse both sides. If both sides return something, this node is the LCA; else pass up whichever side found something.
6. 6Each node is visited once, so these run in O(n) time and O(h) stack space.

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

def diameter(root):
    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)       # longest path bending here, in edges
        return 1 + max(l, r)          # parent only gets one side
    height(root)
    return best

def lca(node, p, q):
    if node is None or node is p or node is q:
        return node
    left = lca(node.left, p, q)
    right = lca(node.right, p, q)
    if left and right:
        return node                   # p and q are on different sides
    return left or right

max_depth is the plain bottom-up template. diameter returns a height to the parent but records left + right as the answer, which counts edges. lca assumes both p and q are in the tree; each runs in O(n) time and O(h) stack space.

Cost: Height, diameter and LCA each visit every node once: O(n) time, O(h) space for the call stack.