Lowest Common Ancestor of a BST

Trees: DFS & BFS, problem 7 of 8

Lowest Common Ancestor of a BST

Medium

LC #235

bstiterative

Not attempted yet

Given the root of a binary search tree and two values p and q that are both in the tree, return the value of their lowest common ancestor: the deepest node that has both p and q in its subtree (a node counts as its own descendant).

Note: here p and q are passed as values (int), and you return the ancestor's value, not the node.

Example 1

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

Example 2

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

2 is an ancestor of 4, and of itself.

Example 3

Input: root = [2, 1], p = 2, q = 1
Output: 2

Constraints

  • 2 ≤ number of nodes ≤ 10^5
  • All values are unique; p ≠ q; both are in the tree.

Python

Loading draft…

Test results

8 tests available

No results yet

Run tests your code against the examples; Submit runs the hidden tests too.

3 examples, 5 hidden

Run examples, then submit all tests.