Find the lowest common ancestor of two given nodes in a binary search tree.
Lowest Common Ancestor of a BST
gfgGiven the root of a binary search tree (BST) and two nodes in the tree, return their lowest common ancestor (LCA).
The lowest common ancestor of two nodes and is the deepest node in the tree that has both nodes as descendants, where a node may be a descendant of itself.
Because the tree is a BST, you can use the ordering property to narrow down where the ancestor must lie.
Input Format
- A binary search tree rooted at
root. - Two nodes
pandqthat are guaranteed to exist in the tree.
In interview settings, the tree is usually provided as node references rather than as a serialized input.
Output Format
Return the node that is the lowest common ancestor of p and q.
Constraints
1 <= number of nodes <= $10^{5}$- Node values are unique.
- Both target nodes exist in the BST.
- The tree satisfies the BST ordering property.
- You may assume the tree is non-empty.
Example 1
Input
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output
6
Explanation
Node 2 is in the left subtree of 6 and node 8 is in the right subtree of 6, so 6 is their lowest common ancestor.
Example 2
Input
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output
2
Explanation
Node 4 lies in the subtree rooted at 2, so 2 is the lowest common ancestor of 2 and 4.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.