Lowest Common Ancestor in BST
You are given the root of a Binary Search Tree (BST) and two node values p and q. Your task is to find and return the value of their Lowest Common Ancestor (LCA).
The Lowest Common Ancestor of two nodes is the lowest node in the tree that has both nodes as descendants (where a node can be a descendant of itself).
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: Node 6 is the lowest common ancestor of nodes 2 and 8.
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, so it is the lowest common ancestor.
Input: root = [2,1], p = 2, q = 1
Output: 2
Explanation: The root node is the lowest common ancestor.
Hint 1
Hint 2
- If both p and q are smaller than the current node, move to the left subtree.
Hint 3
- If both p and q are greater than the current node, move to the right subtree.
Hint 4
- Otherwise, the current node is the **Lowest Common Ancestor
- 1 = Number of nodes = 105
- -10? = Node.data = 10?
Unlock the code editor
Sign in to write, run, and submit your solution against the full test suite.
- Run code against sample & hidden test cases
- Save submissions and track your streak
- Compare with editorial & community solutions