DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Lowest Common Ancestor of a Binary Tree

mediumTrees Must-do

Problem statement

Given the root of 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 in its subtree. A node counts as being in its own subtree, so if p is an ancestor of q, the answer is p.

The tree is not a binary search tree, so values say nothing about position. All values are distinct, and both p and q are in the tree. Trees are written in level order, with null for a missing child.

Examples

Example 1

Input: root = [20, 8, 22, 4, 12, null, null, null, null, 10, 14], p = 10, q = 14

Output: 12

Example 2

Input: root = [20, 8, 22, 4, 12, null, null, null, null, 10, 14], p = 8, q = 10

Output: 8

Explanation: 10 is inside 8's subtree, so 8 is its own lowest common ancestor with 10.

Hints

Approach

Do it in one post-order walk. The function returns p or q if it finds one in the subtree, and None otherwise.

  1. If node is empty, or is p or q, return node.
  2. Recurse into the left and right subtrees.
  3. If both sides return a node, then p is on one side and q on the other, so node is the split point: return node.
  4. Otherwise return whichever side is not empty (or None).

Why step 1 can return early: if node is p and q is somewhere below it, p is the answer, and nothing above will find q elsewhere. If q is in another branch, a higher node will see results from both sides. This relies on both nodes being present in the tree.

ComplexityTime O(n)Space O(h)
Python
from typing import Optional
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def lowestCommonAncestor(self, root: "TreeNode", p: "TreeNode", q: "TreeNode") -> "TreeNode":
if root is None or root is p or root is q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right: # p and q are on different sides
return root
return left or right

Follow-up questions

  • Nodes have a parent pointer and you are not given the root. Find the LCA using O(1) extra space.
  • Find the lowest common ancestor of a whole list of nodes, not just two.

Frequently asked questions

The one-pass version would then return whichever node it found, which is wrong. Count how many of the two targets you actually saw during the walk, and return None unless the count is 2. The path version handles it naturally: if either path is empty, there is no answer.

Yes. In a BST, start at the root and move left while both values are smaller, right while both are larger. The first node where they split, or equal one of them, is the answer, in O(h) time and O(1) space.

Finding the closest shared parent is a common hierarchy question: the common directory of two paths, the lowest shared manager or team in an org tree, or the nearest common commit of two branches (which is what git merge-base finds, though on a graph rather than a tree).