Find Lowest Common Ancestor (LCA) of two nodes in a BST

Given a BST and two nodes x and y in it, find lowest common ancestor (LCA) of x and y in it.

 

The lowest common ancestor (LCA) of two nodes x and y in a BST is the lowest (i.e. deepest) node that has both x and y as descendants, where each node can be descendant of itself (so if x is reachable from w, w is the LCA). In other words, the LCA of x and y is the shared ancestor of x and y that is located farthest from root.
 

For example, consider below BST.

Lowest Common Ancestor of BST

 


 

Simple solution would be to store path from root to x and path from root to y in two auxiliary arrays. Then we traverse both arrays simultaneously till the values in the arrays match. The last matched value will be the LCA. If the end of one array is reached then last seen value is LCA. The time complexity of this solution is O(n) but auxiliary space used by it is O(n) required for storing two arrays.
 

We can recursively find lowest common ancestor of nodes x and y present in the BST. The trick is to find the node in BST which has one key present in its left subtree and the other key present in right subtree. If any such node is present in the tree, then it is LCA else if y lies in subtree rooted at node x, then x is the LCA else if x lies in subtree rooted at node y, then y is the LCA.

 
C++ implementation –
 

Download   Run Code

Output:

LCA is 10

 
The time complexity of above solution is O(n) and need O(h) extra space for the call stack where h is the height of the tree.

 


 

Iterative version –

 

The same algorithm can be easily implemented iteratively.

 
C++ implementation –
 

Download   Run Code

Output:

LCA is 10

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

 
References:https://en.wikipedia.org/wiki/Lowest_common_ancestor

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz