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);
 }
}

Print nth smallest number in tree

import java.util.Vector;

class LocalTree{
 public int val;
 public LocalTree leftTree;
 public LocalTree rightTree;

 /**
  Enter the index here
*/
 public static int NTHSMALLEST = 3;
 public LocalTree(int i) {
  val = i;
 }
 public void add(int i){
  LocalTree temp = this;
  LocalTree parent = this;
  while (temp != null){
   parent = temp;
   if ( i > temp.val){
    temp = temp.rightTree;
   
   }else{
    temp = temp.leftTree;
   }
  }
  temp  = new LocalTree(i);
  if ( i > parent.val){
   parent.rightTree = temp;
  }else{
   parent.leftTree = temp;
  }
 }

 public static void normalTraverse(LocalTree root){
  if (root == null)
   return;
  normalTraverse (root.leftTree);
  System.out.println(root.val);
  normalTraverse (root.rightTree);
 }



 public static int nthSmallest(LocalTree root, int count){
  if (root == null){
   return count;
  }
 
  count = nthSmallest(root.leftTree, count) + 1;
 
 
  if (count == NTHSMALLEST){
   System.out.println("nth smalles element " + root.val);
   System.exit(0);
  }
 
  count =  nthSmallest(root.rightTree, count) ;
 
 
  return count;
 }
}

public class TreePrint {

 public static void main(String[] args) {
       
  LocalTree l = new LocalTree(100);
  l.add(150);
  l.add(125);l.add(124);l.add(126);l.add(175);l.add(170);l.add(180);

  StringBuffer s1 = new StringBuffer();
  StringBuffer s2 = new StringBuffer();
  LocalTree.nthSmallest(l, 0);
 }

}

Print Tree elements in zig-zag order

Ex: if tree is
                         100
                80                 150
                            125                175
                    124          126    170     180        

For the above tree following should be the output
100
150  80
125   175
180   170  126 124

Code:

import java.util.Vector;

class LocalTree{
    public int val;
    public LocalTree leftTree;
    public LocalTree rightTree;

    public int leftChildCount = -1;
    public int rightChildCount = -1;
    public static int maxDistance = -1;
    public static LocalTree maxDistanceRoot = null;

   public static int NTHSMALLEST = 4;
   public LocalTree(int i) {
       val = i;
   }

   public void add(int i){
      LocalTree temp = this;
      LocalTree parent = this;
      while (temp != null){
           parent = temp;
           if ( i > temp.val){
             temp = temp.rightTree;
           }else{
             temp = temp.leftTree;
          }
      }
      temp  = new LocalTree(i);
      if ( i > parent.val){
         parent.rightTree = temp;
      }else{
        parent.leftTree = temp;
     }
 }
 public static void zigZagPrint(LocalTree root){
  if (root == null)
   return;
 // System.out.println(root.val);
  Vector stack1 = new Vector();
  Vector stack2 = new Vector();
 
  //stack1.add(root.rightTree);
  stack2.add(root);
  boolean condition = true;
  while (condition ){
   while (stack1.size() != 0){
      LocalTree currentElem = (LocalTree)stack1.remove(stack1.size()-1);
      System.out.print(currentElem.val + " ");
    
      if (currentElem.rightTree != null)
             stack2.add(currentElem.rightTree);
      if (currentElem.leftTree != null)
            stack2.add(currentElem.leftTree);
   }

   System.out.println();
   while(stack2.size() != 0){
     LocalTree currentElem = (LocalTree)stack2.remove(stack2.size()-1);
    System.out.print(currentElem.val + " ");
     if (currentElem.leftTree != null)
        stack1.add(currentElem.leftTree);
    if (currentElem.rightTree != null)
       stack1.add(currentElem.rightTree);
   }

   System.out.println();
   if (stack1.size() == 0 && stack2.size() == 0)
    condition = false;
  }
 
 }



}

public class TreePrint {

 public static void main(String[] args) {
  LocalTree l = new LocalTree(100);
  l.add(150);
  l.add(80);
  
  l.add(125);
  l.add(124);
  l.add(126);
  l.add(175);
  l.add(170);
  l.add(180);
  LocalTree.zigZagPrint(l);

 }

}

Check whether subsequence sum is equal to given number

public class SubSeqSum {
    static int arr[] = {1, 4, 10, 20, 34};
   static int elemSum = 25;
   Object o;
   public static void main(String[] args) {
      // SubSeqSum.testDynamicApproach();
       boolean found = SubSeqSum.testUsingRecursiveApproach(0, elemSum);
      if (found){
                 System.out.println("Sum FOund");
       }else{
                System.out.println("sum not found");
       }
 }
 private static boolean testUsingRecursiveApproach(int index,int elemSum) {
    if (elemSum == 0){
        return true;
    }
    if ( ((index+1) > arr.length) || (elemSum <0) )
           return false;
 
 
  if ( testUsingRecursiveApproach((index+1), elemSum - arr[index]) || testUsingRecursiveApproach((index+1), elemSum) )
         return true;
  else
         return false;
 
 }
 private static void testDynamicApproach() {
   int temp[] = new int[arr.length];
 
   for (int i=0;i<arr.length;i++){
       for (int j=0;j<(i+1);j++){
            temp[j] = temp[j] + arr[i];
            if (temp[j] == elemSum){
                 System.out.println("Sum foound");
            }
        }
    }

 
 }
}

 

Print Valid bracket pattern of given length

import java.util.HashSet;
import java.util.Set;

public class Paren {
    static Set<String> h = new HashSet();

   static void generateComb(StringBuffer str, int permToGen){
       if (permToGen == 0){
               h.add(str.toString());
              return;
        }
 
       for (int i=0;i<str.length();i++){
            StringBuffer s = new StringBuffer(str);
            s = s.insert(i, "()");
           generateComb(s, permToGen-1);
       }
 
 }


 public static void main(String[] args) {
     StringBuffer str = new StringBuffer("()");
     int permToGen = 3;
     generateComb(str, permToGen-1);
 
      System.out.println("Set lenght " + h.size());
 }
}

Program of combinations to climb steps

Problem Statement: Suppose a person is climbing stairs with "n" steps and at a time a person can climb "x"steps. So what are the different permutations of climbing this stairs

Ex: If there are 5 steps in stair and at a time person can climb maximum 3 steps. Then following are the different permutations

11111
1112
1121
113
1211
122
131
2111
212
221
23
311
32

Code:

public class Steps {
   
  public void findStep(int steps, String buf){
  
   if (steps == 0){
    System.out.println(buf);
    return;
   }else{
    if (steps == 1){
     findStep(steps-1, buf + "1");
    }
    if (steps == 2){
     findStep(steps-1, buf + "1");
     findStep(steps-2, buf + "2");
    }
   
    if (steps >= 3){
     findStep(steps-1, buf + "1");
     findStep(steps-2, buf + "2");
     findStep(steps-3, buf + "3");
    }
   
   
   }
 
 }
 
  public static void main(String[] args) {
   String buf = new String();
   Steps s = new Steps();
   s.findStep(5, buf);
  }
}

I'll try to improve this program and generalize it in next posts

Arrange number in array such that positive and negative occur alternate

Problem Statement: Arrange number in array such that positive and negative occur alternately. And continuous numbers positive or negative should be summed up


public class Consolidate {
    static int arr[] = {3, -6, 10, 4, 7, -6, -5, 4, -1};

 public static void main(String[] args) {
  int j = 0;
  int ord = (arr[0] > 0)? 0 : 1;
  int sum = 0;
  for (int i=0;i<arr.length;i++){
   if ( (arr[i] >0 && ord == 0) || (arr[i] < 0 && ord == 1)){
    sum = sum + arr[i];
   }else{
    ord = (ord+1)%2;
    arr[j++] = sum;
    sum = arr[i];
   }
  }
  arr[j++]= sum;
  for (int i=0;i<j;i++){
   System.out.println(arr[i] + " ");
  }
 }

}