Skip to content
Onsite
16 / 29

Lowest Common Ancestor of a Binary Search Tree

MediumP2Coding

Given a binary search tree and two of its nodes p and q, return their lowest common ancestor: the deepest node that has both p and q among its descendants. A node counts as a descendant of itself.

In this exercise p and q are given as values; the harness passes you the nodes of the tree that hold those values. All values in the tree are unique. Return the ancestor node; it is compared by its value.

Example 1

Input
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output
6

Example 2

Input
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output
2
Why
A node can be its own ancestor.

Constraints

  • 2 <= number of nodes <= 10^5
  • -10^9 <= Node.val <= 10^9
  • All values are unique.
  • p != q and both exist in the tree.

Hints

Run checks the 3 visible tests, Submit all 9.