19  Lowest Common Ancestor of a Binary Tree

Rank 17 · Pattern: recursive postorder aggregation · Target: \(O(n)\) time, \(O(h)\) space

19.1 Problem definition

Given the root of a binary tree and two target nodes p and q, return their lowest common ancestor: the deepest node whose subtree contains both targets.

19.2 Clarifying questions

1. Is the input an ordinary binary tree or a binary search tree?
2. Are p and q node references or values to search for?
3. Are both target nodes guaranteed to exist in the tree?
4. Does a node count as an ancestor of itself?
5. Can p and q refer to the same node?

19.3 Sample answers

1. It is an ordinary binary tree with no ordering guarantee.
2. They are references to specific node objects; compare them by identity.
3. Yes. Both targets are present.
4. Yes. If one target is an ancestor of the other, return that target.
5. Yes. In that case, return the shared target node.

19.4 Special data structure and identity

TreeNode has value, left, and right. Targets identify particular nodes, not merely equal values.

Java

Compare node references with root == p.

Python

Compare objects with root is first.

Rust

The tree owns children with Box, while the algorithm accepts and returns borrowed &TreeNode references. std::ptr::eq compares the identities behind those references, and the return lifetime ties the result to the tree.

       3
      / \
     5   1
    / \
   6   2

LCA(5,2) = 5   because a node can be its own ancestor
LCA(6,1) = 3   because the targets split across root

19.5 Approach and invariant

Postorder recursion asks each subtree whether it contains either target:

1. null contributes no target.
2. A target node returns itself immediately.
3. Recurse left and right.
4. If both return non-null, the current node is the first split point and therefore the LCA.
5. Otherwise propagate the one non-null result.

Invariant: under the both-exist contract, a non-null return from a subtree is either a target found there or the LCA already established inside that subtree.

%%{init: {
  "theme": "base",
  "flowchart": {
    "htmlLabels": false
  },
  "themeVariables": {
    "primaryColor": "#ffffff",
    "secondaryColor": "#ffffff",
    "tertiaryColor": "#ffffff",
    "primaryTextColor": "#222222",
    "primaryBorderColor": "#555555",
    "lineColor": "#555555",
    "edgeLabelBackground": "#ffffff"
  }
}}%%
flowchart TB
  A["Visit the current node"]
  B{"Is it null, p, or q?"}
  C["YES: return the current node"]
  D["NO: recursively search left and right"]
  E{"Did both searches return a node?"}
  F["YES: return the current split point"]
  G["NO: return whichever result is non-null"]

  A --> B
  B --> C
  B --> D
  D --> E
  E --> F
  E --> G

  classDef plain fill:#ffffff,stroke:#555555,stroke-width:1.5px,color:#222222;
  class A,B,C,D,E,F,G plain;

19.6 Minimal solution

Java

import java.util.*;
import org.junit.*;
import org.junit.runner.*;
import static org.junit.Assert.*;

public class LowestCommonAncestorSolution {
    static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;
        TreeNode(int value) { this.value = value; }
    }

    static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        }
        if (left != null) {
            return left;
        }
        return right;
    }

    @Test public void findsSplitPoint() {
        TreeNode root = new TreeNode(3);
        TreeNode five = new TreeNode(5);
        TreeNode one = new TreeNode(1);
        root.left = five;
        root.right = one;
        five.left = new TreeNode(6);
        five.right = new TreeNode(2);
        assertSame(root, lowestCommonAncestor(root, five, one));
    }

    @Test public void nodeCanBeItsOwnAncestor() {
        TreeNode root = new TreeNode(3);
        TreeNode five = new TreeNode(5);
        TreeNode two = new TreeNode(2);
        root.left = five;
        five.right = two;
        assertSame(five, lowestCommonAncestor(root, five, two));
    }

    @Test public void findsParentOfSiblingLeaves() {
        TreeNode root = new TreeNode(3);
        TreeNode left = new TreeNode(6);
        TreeNode right = new TreeNode(2);
        root.left = left;
        root.right = right;
        assertSame(root, lowestCommonAncestor(root, left, right));
    }

    @Test public void returnsTargetWhenBothReferencesAreTheSame() {
        TreeNode root = new TreeNode(3);
        TreeNode target = new TreeNode(5);
        root.left = target;
        assertSame(target, lowestCommonAncestor(root, target, target));
    }

    @Test public void findsDeepAncestorWithinOneSubtree() {
        TreeNode root = new TreeNode(3);
        TreeNode five = new TreeNode(5);
        TreeNode two = new TreeNode(2);
        TreeNode seven = new TreeNode(7);
        TreeNode four = new TreeNode(4);
        root.left = five;
        five.right = two;
        two.left = seven;
        two.right = four;

        assertSame(two, lowestCommonAncestor(root, seven, four));
    }

    @Test public void comparesTargetsByIdentityNotValue() {
        TreeNode root = new TreeNode(0);
        TreeNode expected = new TreeNode(5);
        TreeNode p = new TreeNode(1);
        TreeNode q = new TreeNode(2);
        root.left = expected;
        expected.left = p;
        expected.right = q;
        root.right = new TreeNode(1);

        assertSame(expected, lowestCommonAncestor(root, p, q));
    }

    public static void main(String[] args) {
        JUnitCore.main("LowestCommonAncestorSolution");
    }
}

Python

import unittest


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


def lowest_common_ancestor(root, first, second):
    if root is None or root is first or root is second:
        return root

    left = lowest_common_ancestor(root.left, first, second)
    right = lowest_common_ancestor(root.right, first, second)

    if left is not None and right is not None:
        return root
    return left if left is not None else right


class LowestCommonAncestorTests(unittest.TestCase):
    def test_finds_split_point(self):
        five = TreeNode(5, TreeNode(6), TreeNode(2))
        one = TreeNode(1)
        root = TreeNode(3, five, one)
        self.assertIs(root, lowest_common_ancestor(root, five, one))

    def test_node_can_be_its_own_ancestor(self):
        two = TreeNode(2)
        five = TreeNode(5, right=two)
        root = TreeNode(3, left=five)
        self.assertIs(five, lowest_common_ancestor(root, five, two))

    def test_same_target_reference(self):
        target = TreeNode(5)
        root = TreeNode(3, left=target)
        self.assertIs(target, lowest_common_ancestor(root, target, target))

    def test_finds_deep_ancestor(self):
        seven = TreeNode(7)
        four = TreeNode(4)
        two = TreeNode(2, seven, four)
        root = TreeNode(3, TreeNode(5, right=two))
        self.assertIs(two, lowest_common_ancestor(root, seven, four))

    def test_compares_targets_by_identity(self):
        first = TreeNode(1)
        second = TreeNode(2)
        expected = TreeNode(5, first, second)
        root = TreeNode(0, expected, TreeNode(1))
        self.assertIs(expected, lowest_common_ancestor(root, first, second))


if __name__ == "__main__":
    unittest.main()

Rust

#[derive(Debug)]
pub struct TreeNode {
    pub value: i32,
    pub left: Link,
    pub right: Link,
}

pub type Link = Option<Box<TreeNode>>;

impl TreeNode {
    pub fn new(value: i32) -> Self {
        Self {
            value,
            left: None,
            right: None,
        }
    }
}

pub fn lowest_common_ancestor<'a>(
    root: Option<&'a TreeNode>,
    first: &TreeNode,
    second: &TreeNode,
) -> Option<&'a TreeNode> {
    let root = root?;
    if std::ptr::eq(root, first) || std::ptr::eq(root, second) {
        return Some(root);
    }

    let left = lowest_common_ancestor(root.left.as_deref(), first, second);
    let right = lowest_common_ancestor(root.right.as_deref(), first, second);

    match (left, right) {
        (Some(_), Some(_)) => Some(root),
        (Some(node), None) | (None, Some(node)) => Some(node),
        (None, None) => None,
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn node(value: i32) -> Box<TreeNode> {
        Box::new(TreeNode::new(value))
    }

    #[test]
    fn finds_split_point() {
        let mut five = node(5);
        five.left = Some(node(6));
        five.right = Some(node(2));
        let one = node(1);
        let mut root = node(3);
        root.left = Some(five);
        root.right = Some(one);

        let first = root.left.as_deref().unwrap();
        let second = root.right.as_deref().unwrap();
        let result = lowest_common_ancestor(Some(&root), first, second).unwrap();
        assert!(std::ptr::eq(result, root.as_ref()));
    }

    #[test]
    fn node_can_be_its_own_ancestor() {
        let mut five = node(5);
        five.right = Some(node(2));
        let mut root = node(3);
        root.left = Some(five);

        let first = root.left.as_deref().unwrap();
        let second = first.right.as_deref().unwrap();
        let result = lowest_common_ancestor(Some(&root), first, second).unwrap();
        assert!(std::ptr::eq(result, first));
    }

    #[test]
    fn same_target_reference() {
        let mut root = node(3);
        root.left = Some(node(5));
        let target = root.left.as_deref().unwrap();
        let result = lowest_common_ancestor(Some(&root), target, target).unwrap();
        assert!(std::ptr::eq(result, target));
    }

    #[test]
    fn compares_targets_by_identity() {
        let mut expected = node(5);
        expected.left = Some(node(1));
        expected.right = Some(node(2));
        let mut root = node(0);
        root.left = Some(expected);
        root.right = Some(node(1));

        let expected = root.left.as_deref().unwrap();
        let first = expected.left.as_deref().unwrap();
        let second = expected.right.as_deref().unwrap();
        let result = lowest_common_ancestor(Some(&root), first, second).unwrap();
        assert!(std::ptr::eq(result, expected));
    }
}

19.7 High-value tests

Relationship	Expected
targets in opposite root subtrees	root
one target ancestor of other	ancestor target
targets are sibling leaves	their parent
deep targets on one side	LCA inside that side
p == q, if allowed	that node

19.8 Complexity and correctness

In the worst case, all \(n\) nodes are visited: \(O(n)\) time. Recursion uses \(O(h)\) stack space.

If targets occur in different child subtrees, the current node is their deepest common ancestor because neither child contains both. If both are in one child, the other return is null and the already-discovered target or LCA propagates. Returning a target immediately correctly handles the case where it is ancestor of the other under the both-exist guarantee.

19.9 If the interviewer pushes

• If either target may be absent, return a result carrying both a candidate and a count; accept an LCA only when two targets were found.
• With parent pointers, walk ancestors of one node into a set, then climb the other.
• In a BST, compare both target values with the current value and descend left or right until they split, taking \(O(h)\) time.
• For many LCA queries on one static tree, preprocessing techniques trade setup and memory for faster queries.

19.10 TDD interview script

Confirm this is an ordinary tree, targets are node references guaranteed present, identity determines a match, a node is its own ancestor, and p == q is allowed. Then write this test list:

1. Root split
2. Ancestor target
3. Sibling leaves
4. Identical target references
5. Deep LCA within one subtree
6. Unrelated equal-valued nodes

Add one focused red–green–refactor cycle per relationship. Build explicit node references, assert returned node identity with the language’s identity operation, and rerun the complete example after each step. A value-only assertion cannot verify the identity contract.

From book/src, run:

Java

./java/run.sh LowestCommonAncestorSolution

Python

./python/run.sh lowest_common_ancestor_solution

Rust

./rust/run.sh lowest_common_ancestor_solution

Describe each recursive return as a summary: null means neither target was found in that subtree; a non-null node is a target or an LCA already established below. Two non-null child summaries make the current node the split point.

19.10.1 Pseudocode

lca(node, p, q):
    if node is null 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 are both non-null:
        return node
    if left is non-null:
        return left
    return right

Under the both-present contract, a non-null subtree result is either one target or the lowest common ancestor already determined inside that subtree.

19.10.2 TDD sequence

Step	Test code added	Production code added or changed
1. Targets split at root	findsSplitPoint	Recurse into both children and return the current node when both results are non-null.
2. Ancestor is a target	nodeCanBeItsOwnAncestor	Return immediately when the current node is p or q, allowing it to be its own ancestor.
3. Smallest split	findsParentOfSiblingLeaves	Triangulate the postorder combination at the direct parent of both targets.
4. Same target twice	returnsTargetWhenBothReferencesAreTheSame	The identity base case returns the shared target without requiring two separate discoveries.
5. Propagate internal LCA	findsDeepAncestorWithinOneSubtree	When only one child returns non-null, propagate that result unchanged through ancestors.
6. Identity contract	unrelated equal-valued node	Compare node identity, not values; an unrelated equal-valued node must contribute nothing.

The sequence exercises all three postorder summaries—none, one, and both—then uses an adversarial equal-value fixture to prevent a value-based implementation.