Lowest common ancestor of two nodes

Question

In a binary tree, the lowest common ancestor (LCA) of two nodes p and q is the deepest node that has both p and q in its subtree (a node can be its own ancestor). Return that node.

        3
       / \
      5   1
     / \
    6   2
LCA(6, 2) -> 5
LCA(6, 1) -> 3

Return the LCA node of p and q. Assume both nodes exist in the tree.

Accepted Answer

Recurse from the root. If the current node is null or is one of the targets, return it. Otherwise search both subtrees. If both sides return a non-null result, the two targets lie on opposite sides, so the current node is the LCA. If only one side is non-null, the LCA is somewhere down that side, so propagate it up. Tracing LCA(6, 2): node 5 finds 6 on its left and 2 on its right, so it is returned; the search above 5 sees only one non-null side and passes 5 upward. Time O(n), space O(h) recursion depth. Edge cases: if one target is an ancestor of the other, the ancestor itself is returned (t…

Lowest common ancestor of two nodes

Your answer

More Coding questions