Thursday, May 1, 2014

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

}

No comments:

Post a Comment