‹ DS&A interview · Socratic
DSA · Trees · #107

Lowest Common Ancestor of a Binary Tree

Module 44 · difficulty 3/5·⏱ 30:00starts on first keystroke

Given the `root` of a binary tree and two distinct nodes `p` and `q` present in the tree, return their **lowest common ancestor (LCA)**. The LCA of `p` and `q` is the deepest node in the tree that has both `p` and `q` as descendants, where a node is allowed to be a descendant of itself. Implement `lowestCommonAncestor(root, p, q)`. The arguments `p` and `q` are references to actual nodes in the tree (object identity), and node values are unique. Return the node reference of the LCA. Each node has the shape `{ val, left, right }`.

Examples
  • root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 → 3 — Nodes 5 and 1 sit in the left and right subtrees of 3, so 3 is their LCA.
  • root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 → 5 — Node 4 is a descendant of 5, and a node can be a descendant of itself, so the LCA is 5.
  • root = [1,2], p = 1, q = 2 → 1
Constraints
  • · The number of nodes is in the range [2, 10^5].
  • · -10^9 <= Node.val <= 10^9
  • · All Node.val are unique.
  • · p != q and both p and q exist in the tree.
  • · p and q are passed as node references, not values.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.