Least Common Ancestor (LCA) problem.

You are given pointer to the root of the binary search tree and two values  and . You need to return the lowest common ancestor (LCA) of v1 and v2  in the binary search tree.

In the diagram above, the lowest common ancestor of the nodes 4 and 6 is the node 3 . Node 3  is the lowest node which has nodes 4  and 6 as descendants.

CODE :

public static Node lca(Node root, int v1, int v2) {
if(root==null)return null;
Node curr=root;
while(curr!=null)
{
if(curr.data > v1 && curr.data >v2){
curr=curr.left;
}
else if(curr.data < v1 && curr.data <v2 ){
curr=curr.right;
}
else{
return curr;
}
}
return curr;
}

PROBLEM LINK : https://www.hackerrank.com/challenges/binary-search-tree-lowest-common-ancestor/problem

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Create your website at WordPress.com
Get started
%d bloggers like this: