Thursday, May 1, 2014

Program to filter values not in range from BST

Problem Statement: Remove the values from the Binary search tree which are out of the given range

Ex: Input tree



 Input Range: 10 to 16

Output Values:  10, 12, 13, 14, 16

Code:

class LocalTree2{
     public int val;
  public LocalTree2 leftTree;
  public LocalTree2 rightTree;
  static int MIN = 9;
  static int MAX = 11;
  static public LocalTree2 init;
  public LocalTree2(int i) {
   val = i;
  }
  public void add(int i){
   LocalTree2 temp = this;
   LocalTree2 parent = this;
   while (temp != null){
    parent = temp;
    if ( i > temp.val){
     temp = temp.rightTree;
 
    }else{
     temp = temp.leftTree;
    }
   }
   temp  = new LocalTree2(i);
   if ( i > parent.val){
    parent.rightTree = temp;
   }else{
    parent.leftTree = temp;
   }
  }


  public LocalTree2 deleteFromTree(LocalTree2 tree, int value){
   if (tree == null)
    return tree;

   if (tree.val < value){
       tree.rightTree = deleteFromTree(tree.rightTree, value);
   }else{
    if (tree.val > value){
     tree.leftTree = deleteFromTree(tree.leftTree, value);
    }else{
     LocalTree2 successorNode = getInOrderSucessor2(tree);
     if (successorNode != null){
      tree.val = successorNode.val;
      tree.rightTree = deleteFromTree(tree.rightTree, tree.val);
     }else{
      tree = tree.leftTree;
     }
    }

   }
   return tree;
  }


  private int getInOrderSucessor(LocalTree2 node) {
   if (node.rightTree != null){
    node = node.rightTree;
   }
    while (node.leftTree != null ){
     node = node.leftTree;
    }
   return node.val;

  }
  private LocalTree2 getInOrderSucessor2(LocalTree2 node) {
   if (node == null || node.rightTree == null){
    return null;
   }
   node = node.rightTree;
    while (node.leftTree != null ){
     node = node.leftTree;
    }
   return node;

  }

  public void printTree(LocalTree2 root){
   if (root == null)
    return;
   printTree(root.leftTree);
   System.out.println(root.val);
   printTree(root.rightTree);
  }

  public LocalTree2 findNode(LocalTree2 root, int val){
   if (root == null)
    return null;

   LocalTree2 node = findNode(root.leftTree, val);
   if ( node != null)
    return node;
   if (root.val == val)
    return root;
   node = findNode(root.rightTree, val);
   if ( node != null)
    return node;
   return null;
  }

  public LocalTree2 filterNode(LocalTree2 tree, int minFilter, int maxFilter){
   if (tree == null)
    return tree;

   tree.leftTree = filterNode(tree.leftTree, minFilter, maxFilter);
   while (tree != null &&  ((tree.val < minFilter) || (tree.val > maxFilter) )){
    tree = deleteFromTree(tree, tree.val);
   }
   if (tree != null)
    tree.rightTree = filterNode(tree.rightTree, minFilter, maxFilter);


   return tree;

  }

}

public class BST {
 public static void main(String[] args) {
  LocalTree2 l = new LocalTree2(8);
  l.add(3);
  l.add(1);
  l.add(6);
  l.add(4);
  l.add(7);
  l.add(10);
  l.add(14);
  l.add(13);
  l.add(12);
  l.add(16);
  l.printTree(l);
  l = l.filterNode(l, 10, 16);
  System.out.println("************** Post Filtering ********************");
  l.printTree(l);
 }
}

No comments:

Post a Comment