Tuesday, November 15, 2011

LCA of two given nodes in BST






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