Lowest Common Ancestor of a Binary Tree

Problem (restated)

Given a binary tree and two nodes p and q, return their lowest common ancestor (deepest node that has both as descendants).

Intuition

If left finds one and right finds the other, this node is LCA. If both under one side, return that side.

Approaches

export class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

export function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode | null,
  q: TreeNode | null,
): TreeNode | null {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left ?? right;
}

export class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

export function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode | null,
  q: TreeNode | null,
): TreeNode | null {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left ?? right;
}

Template connection

Tree DFS return subtree witness.

Reflection

• Post-order: look left, then right. Both sides found something: this node is the ancestor. Only one side did: pass that result up.
• If this node is p or q, return it. When one node sits under the other, the ancestor is the node you already found.
• p == q is that node. Both nodes are in the tree. The root is always an upper bound.