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.
- 1 = Number of nodes = 105
- -10? = Node.data = 10?
- Using the BST property:
- If both p and q are smaller than the current node, move to the left subtree.
- If both p and q are greater than the current node, move to the right subtree.
- Otherwise, the current node is the **Lowest Common Ancestor
See how the best solutions work
Approach, complexity and clean code in every language. Sign in to unlock the editorial.
Keep every attempt
Your submissions, results and runtime history live here. Sign in to start your streak.
50 30 70 20 40 60 80 20 40
30
40 20 60 10 30 50 70 10 70
40