public class LCA {
LCA left;
LCA right;
int data;
LCA(int data){
this.data=data;
}
public static void main(String[] args) {
LCA root=new LCA(20);
insert(root,8);
insert(root,12);
insert(root,4);
insert(root,22);
insert(root,14);
insert(root,10);
preorder(root);
find_lca(root,14,4);
}
public static void insert(LCA node,int data){
if(node.data > data){
if(node.left!=null)
insert(node.left,data);
else
node.left=new LCA(data);
}
if(node.data < data){
if(node.right!=null)
insert(node.right,data);
else
node.right=new LCA(data);
}
}
public static void find_lca(LCA root, int data1, int data2){
if(root.data == data1 || root.data == data2){
System.out.println("One of the given input is root node. No LCA");
return;
}
while(root!=null ){
if(root.left ==null || root.right==null) {
System.out.println("One or both of the datas given is not existing in the tree");
break;
}
else if(root.data < data1 && root.data < data2){
if(root.right.data == data1 || root.right.data == data2){
System.out.println("LCA : " + root.data);
break;
}
root=root.right;
}
else if(root.data > data1 && root.data > data2){
if(root.left.data == data1 || root.left.data == data2){
System.out.println("LCA : " + root.data);
break;
}
root=root.left;
}
else{
System.out.println("LCA of" + data1 + "and" + data2 + "is" + root.data);
break;
}
}
}
public static void preorder(LCA root){
if(root!=null) {
System.out.println(root.data);
preorder(root.left);
preorder(root.right);
}
}
}
Recursive :
http://www.cracktheinterview.in/viewtopic.php?f=2&t=92&sid=9fb3ab9e038d3641cb5f39e3b6f3c777
No comments:
Post a Comment