28. Lowest Common Ancestor in a BST
Last updated
Was this helpful?
Last updated
Was this helpful?
The problem can be found at the following link:
To find the Lowest Common Ancestor (LCA) of two nodes in a Binary Search Tree (BST), I used the property of a BST where the left subtree contains nodes with values less than the root node, and the right subtree contains nodes with values greater than the root node. Starting from the root, we can traverse down the tree until we find a node whose value lies between the given two nodes, n1 and n2. This node would be the LCA.
The steps involved in our approach are as follows:
Start from the root node.
Compare the data of the current node with the values of n1
and n2
.
If both n1
and n2
are smaller than the current node's value, move to the left subtree and repeat step 2.
If both n1
and n2
are greater than the current node's value, move to the right subtree and repeat step 2.
If the current node's value lies between n1
and n2
(inclusive), it is the LCA.
Time Complexity: O(h)
, where h
is the height of the BST. In the worst case, the height of the BST can be O(n)
, but in a balanced BST, it will be O(log n)
.
Auxiliary Space Complexity: O(h)
as well, due to the recursive calls made during the traversal. In the worst case, it can be O(n)
if the tree is skewed, but in a balanced BST, it will be O(log n)
.
For discussions, questions, or doubts related to this solution, please visit our . We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star
to the repository.