Lowest Common Ancestor in a BST
Find the lowest common ancestor of two given values in a binary search tree, using the tree's ordering to avoid a generic tree search.
Given the root of a binary search tree (BST) and two integers p and q, both guaranteed to be values that exist somewhere in the tree, return the value of their lowest common ancestor (LCA).
The lowest common ancestor of two nodes p and q is defined as the deepest node in the tree that has both p and q as descendants (a node is allowed to be a descendant of itself).
Because the tree is a BST, you should take advantage of its ordering property to find the answer more efficiently than a generic tree-search approach would.
Example 1
Input: root = [5,3,8,2,4,7,9], p = 2, q = 4
Output: 3
Explanation: 2 and 4 are both in the left subtree rooted at 3, and 3 is their lowest common ancestor.
Example 2
Input: root = [5,3,8,2,4,7,9], p = 2, q = 9
Output: 5
Explanation: 2 is in the left subtree and 9 is in the right subtree of the root, so the root itself is the split point.
Example 3
Input: root = [5,3,8,2,4,7,9], p = 7, q = 8
Output: 8
Explanation: 8 is an ancestor of 7, so 8 is its own lowest common ancestor with 7.
Constraints
- The number of nodes in the tree is in the range [2, 10000].
- -1000000 <= Node.val <= 1000000
- p and q are guaranteed to both exist in the tree, and p != q.
- root is guaranteed to be a valid binary search tree.
- All node values are unique.
Follow-up
How would this differ if you were given a generic binary tree with no ordering guarantee?
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.