15. Lowest Common Ancestor in a BST
The problem can be found at the following link: Question Link
Problem Description
Given a Binary Search Tree (BST) with unique values and two nodes n1
and n2
(where n1 != n2
), find the Lowest Common Ancestor (LCA) of the two given nodes in the BST.
The LCA is the lowest node in the BST that has both n1
and n2
as descendants (a node is also considered its own descendant).
Examples
Example 1:
Input:
5
/ \
4 6
/ \
3 7
\
8
n1 = 7
, n2 = 8
Output:
7
Explanation:
The lowest common ancestor of 7
and 8
is 7
itself.
Example 2:
Input:
20
/ \
8 22
/ \
4 12
/ \
10 14
n1 = 8
, n2 = 14
Output:
8
Explanation:
8
is the lowest node that is an ancestor of both 8
and 14
.
Example 3:
Input:
2
/ \
1 3
n1 = 1
, n2 = 3
Output:
2
Explanation:
2
is the lowest node that is an ancestor of both 1
and 3
.
Constraints:
$(1 \leq \text{Number of Nodes} \leq 10^5)$
$(1 \leq \text{node->data} \leq 10^5)$
$(1 \leq \text{Node Value}, n1, n2 \leq 10^5)$
My Approach
Iterative Approach (O(H) Time, O(1) Space)
Start from the root of the BST.
If
root->data
is greater than bothn1
andn2
, move to the left subtree.If
root->data
is smaller than bothn1
andn2
, move to the right subtree.Otherwise, return
root
as it is the Lowest Common Ancestor (LCA).
Algorithm Steps:
Start at the root node.
While
root
is notNULL
:If
root->data > max(n1, n2)
, move left.If
root->data < min(n1, n2)
, move right.Otherwise, root is the LCA, return it.
Time and Auxiliary Space Complexity
Expected Time Complexity:
O(H)
, whereH
is the height of the BST. In a balanced BST,H = log N
, so this is efficient.Expected Auxiliary Space Complexity:
O(1)
, as no additional data structures are used.
Code (C++)
class Solution {
public:
Node* LCA(Node* root, Node* n1, Node* n2) {
while (root && (root->data > max(n1->data, n2->data) || root->data < min(n1->data, n2->data)))
root = (root->data > n1->data) ? root->left : root->right;
return root;
}
};
Code (Java)
class Solution {
Node LCA(Node root, Node n1, Node n2) {
while (root != null && (root.data > Math.max(n1.data, n2.data) || root.data < Math.min(n1.data, n2.data)))
root = (root.data > n1.data) ? root.left : root.right;
return root;
}
}
Code (Python)
class Solution:
def LCA(self, root, n1, n2):
while root and (root.data > max(n1.data, n2.data) or root.data < min(n1.data, n2.data)):
root = root.left if root.data > n1.data else root.right
return root
Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Letβs make this learning journey more collaborative!
β If you find this helpful, please give this repository a star! β
πVisitor Count
Last updated