Lowest Common Ancestor of a Binary Tree

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

    Problem statement

    Given a binary tree and two of its nodes p and q, return their lowest common ancestor: the deepest node that has both p and q as descendants. A node counts as a descendant of itself. Both nodes are guaranteed to be in the tree, and values are unique.

    The tree here is a plain binary tree, not a BST, so you can't steer by comparing values. The elegant answer lets each subtree report what it found and lets the first node that hears from both sides declare itself the answer. Original problem: LeetCode 236.

    Example

    For p = 6 and q = 4, both sit under node 5, and no deeper node contains both, so the LCA is 5.
    For p = 6 and q = 4, both sit under node 5, and no deeper node contains both, so the LCA is 5.
    Tree:   [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]
    p = 6, q = 4  ->  5
    p = 5, q = 4  ->  5      # a node is its own ancestor
    p = 6, q = 8  ->  3

    Constraints (assumed)

    • 2 ≤ nodes ≤ 100,000; values unique.
    • p ≠ q, and both exist in the tree.

    What this question tests

    • Postorder recursion that combines results from both children.
    • Defining exactly what a recursive call returns.
    • Knowing when the BST shortcut applies and when it doesn't.

    Questions to ask first

    1. Is it a BST? (Here: no. In a BST you can walk down by comparing values in O(h).)
    2. Are p and q guaranteed to exist? (Here: yes. If not, you must confirm both were found.)
    3. Do nodes have parent pointers? If yes, it becomes "intersection of two linked lists".
    4. Can p be an ancestor of q? (Yes; then p is the answer.)