All problems

Lowest Common Ancestor of a Binary Search Tree

Medium · tree dfs

You are given the root of a binary search tree (BST) and two integers p and q. Return the value of their lowest common ancestor (LCA): the deepest node that has both the node holding p and the node holding q in its subtree. A node counts as a descendant of itself, so if p is an ancestor of q, the answer is p.

Inputs cross the wire as plain values, so p and q are values, not node references. Both are guaranteed to exist in the tree, and all values in the tree are distinct, so each value picks out exactly one node. p and q may be equal. Return the LCA's value as an int.

The tree is a valid BST: every value in a left subtree is smaller than its node, and every value in a right subtree is larger.

Examples

Example 1

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

Output: 6

2 is in the left subtree of 6 and 8 is in the right subtree, so 6 is the first node where they split.

Example 2

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

Output: 2

4 sits below 2, and a node is its own descendant, so the LCA is 2 itself.

Example 3

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

Output: 2

Constraints

• The number of nodes n is in the range [1, 500].
• -10^4 <= Node.val <= 10^4, and all values are distinct.
• The tree is a valid binary search tree.
• p and q both exist in the tree. They may be equal.