Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
public class LowestCommonAncestorBT {
public Node getLCA(Node root, Node n1, Node n2){
if(root==null){
return null;
}else{
if(root.data==n1.data||root.data==n2.data){
return root;
}
Node left = getLCA(root.left,n1,n2);
Node right = getLCA(root.right,n1,n2);
if(left!=null && right!=null){
return root;
}
if(left!=null){
return left;
}else if(right!=null){
return right;
}
return null;
}
}
public static void main (String[] args) throws java.lang.Exception
{
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
Node n3 = new Node(5);
root.left.right = n3;
root.right.left = new Node(6);
root.right.right = new Node(7);
Node n1 = new Node(8);
root.left.left.left = n1;
root.left.left.right = new Node(9);
root.left.right.left = new Node(10);
root.left.right.right = new Node(20);
root.left.right.left.left = new Node(11);
Node n2 = new Node(30);
root.left.right.left.right = n2 ;
LowestCommonAncestorBT i = new LowestCommonAncestorBT();
Node x = i.getLCA(root,n1,n2);
System.out.println("Lowest Common Ancestor ("+n1.data+", "+ n2.data +" ) is " + x.data);
x = i.getLCA(root,n2,n3);
System.out.println("Lowest Common Ancestor ("+n2.data+", "+ n3.data +" ) is " + x.data);
}
}
class Node{
int data;
Node left;
Node right;
public Node (int data){
this.data = data;
left = null;
right = null;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment