Big O Practice: Lowest Common Ancestor

def lca(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right:
        return root
    return left or right

Variables

• n - number of nodes in the tree
• h - height of the tree

Explanation

In the worst case the recursion visits every node - **O(n)** time. Recursion depth equals tree height **O(h)** - `log n` balanced, `n` degenerate. The post-order pattern (recurse first, decide after) is the trick that makes this concise.

More Big O practice problems · Today's daily problem