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

Lowest Common Ancestor of a Binary Search Tree

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

Given the root of a binary search tree (BST) and two existing nodes `p` and `q` in it, return the **lowest common ancestor (LCA)** of `p` and `q`. The LCA is the lowest node in the tree that has both `p` and `q` as descendants, where a node is allowed to be a descendant of itself. Nodes are represented as objects `{ val, left, right }`. Implement `function lowestCommonAncestor(root, p, q)` which receives the actual node objects `p` and `q` (not just their values) and returns the LCA **node**. All node values in the tree are unique.

Examples
  • root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 → 6 — Nodes 2 and 8 sit on opposite sides of 6, so 6 is their LCA.
  • root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 → 2 — 4 is a descendant of 2, and a node can be a descendant of itself.
  • root = [2,1], p = 2, q = 1 → 2
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 BST.
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.