Lowest Common Ancestor of a Binary Search Tree

Given the root of a binary search tree and two node values, return the value of their lowest common ancestor. Pattern focus: LCA in BST. In a BST, the split point where one value goes left and the other goes right is the answer.

Input Format

root = binary tree root, p = first node value, q = second node value

Output Format

value of the lowest common ancestor

Constraints

  • 1 <= number of nodes <= 10^5
  • -10^9 <= node values <= 10^9
  • root, p and q must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

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

Output:

6

Explanation:

The paths to 2 and 8 diverge at the root 6.

Example 2:

Input:

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

Output:

2

Explanation:

Node 2 is an ancestor of node 4.

Loading...
Lowest Common Ancestor of a Binary Search Tree