Thursday, May 1, 2014

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

 }

}

No comments:

Post a Comment