Java : Print n-Tree level by level

Problem: for a n-tree where each node contains any no of nodes print the nodes in level order and each level must contain a line with a gap

Reference : http://www.careercup.com/question?id=3756903

Program :

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package careercup.google;
import java.util.ArrayList;
/**
 *
 * @author Harit
 */
public class NTreeNode {
    private int value;
    private ArrayList<NTreeNode> child;

    public NTreeNode(int v){
        this.value = v;
    }

    public void addChild(NTreeNode n){
        if(child == null){
            child = new ArrayList<NTreeNode>();
        }
        child.add(n);
    }

    public int getValue(){
        return this.value;
    }

    public ArrayList<NTreeNode> getChild(){
        return this.child;
    }
}

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package careercup.google;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

/**
 *
 * @author Harit
 */
public class PrintNTree {

    private static final int INCREMENT = 2; // controls the tree size
    private static int start = 1;
    private static int end = INCREMENT;
    private static Queue<NTreeNode> one = new LinkedList<NTreeNode>();
    private static Queue<NTreeNode> two = new LinkedList<NTreeNode>();

    public static void main(String args[]){
        NTreeNode root = new NTreeNode(0);
        addChildren(root, start,end);
        increment();

        // level one filling
        Iterator l1 = root.getChild().iterator();
        while(l1.hasNext()){
            addChildren((NTreeNode)l1.next(), start, end );
            increment();
        }

        // level two filling
        Iterator l2 = root.getChild().iterator();
        while(l2.hasNext()){
            Iterator l21 = ((NTreeNode)l2.next()).getChild().iterator();
            while(l21.hasNext()){
                addChildren((NTreeNode)l21.next(), start, end);
                increment();
            }
        }
        printLevelList(root);
    }

    private static void addChildren(NTreeNode parent, int start, int end){
        for(int i=start; i<=end; i++){
            NTreeNode node = new NTreeNode(i);
            parent.addChild(node);
        }
    }

    private static void printLevelList(NTreeNode root){
       if(root == null){
           System.out.println("Empty tree");
           return;
       }
       System.out.println( root.getValue() + "");
       System.out.println("-----------------------");
       if(root.getChild() == null){
           System.out.println("No Children");
           return;
       }
       addtoQueue(root.getChild());
       copyQueue();
       while(true){
           while(!one.isEmpty()){
                NTreeNode node = one.remove();
                System.out.print(node.getValue() + " ");
                addtoQueue(node.getChild());
           }
           System.out.println("");
           System.out.println("---------------------------");
           copyQueue();
           if(one.isEmpty() && two.isEmpty()){
               return;
           }

       }
    }

    private static void addtoQueue(ArrayList<NTreeNode> n){
        if(n == null){
            return;
        }
        Iterator iter = n.iterator();
        while(iter.hasNext()){
            two.add((NTreeNode)iter.next());
        }
    }

    private static void copyQueue(){
        while(!two.isEmpty()){
            one.add(two.remove());
        }
    }
    private static void increment(){
        start = end + 1;
        end = start + (INCREMENT - 1);
    }
}

Output:

run:

0

———————–

1 2

—————————

3 4 5 6

—————————

7 8 9 10 11 12 13 14

—————————

BUILD SUCCESSFUL (total time: 0 seconds)

Removing duplicates from array using Binary Search Tree

Problem : given an array e.g. [3,5,4,2,1,2,3,1]

Need : filter the array such as to remove duplicates ( reference : http://www.careercup.com/question?id=3515013)

Approach: There are many ways to do this

a.) sort the array and compare elements in sequential fashion and remove duplicates : Complexity – O(nlogn)

b.) create a hash and based on hash function put values in hash only once, if you encounter duplicates, ignore them : Complexity - O(n)

c.) another approach is to do it with using Binary Search Tree, pick one element at a time, search if it exists in tree, if not, create node, set pointers and if you encounter duplicates, just ignore them by not creating tree nodes: Complexity - O(n)

I tried doing this using Java, took a long time to get it right, but finally it worked. The program also prints the three traversal techniques that we can run on a tree – PreOrder, PostOrder and InOrder

Please note that in code, left=true means ” left child” and left=false means “right child”.

Program is as follows:

BSTNode.java

     /*
     * To change this template, choose Tools | Templates
     * and open the template in the editor.
     */

    package careercup.google;

    /**
     *
     * @author Harit
     */
    public class BSTNode {
        private int value;
        private int leftChild;
        private int rightChild;

        public BSTNode(int v){
            value = v;
            leftChild = -1;
            rightChild = -1;
        }

        public int getValue(){
            return this.value;
        }

        public int getChild(boolean left){
            if(left){
                return this.leftChild;
            }
            else{
                return this.rightChild;
            }
        }
        public void setChild(int child, boolean left){
            if(left){
                this.leftChild = child;
            }else{
                this.rightChild = child;
            }
        }
    }

RemDupArrayBST.java

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package careercup.google;

import java.util.ArrayList;

/**
 *
 * @author Harit
 */
public class RemDupArrayBST {
    /* Output Array of Nodes */
    private static ArrayList<BSTNode> nodes = new ArrayList<BSTNode>();
    private static int parent = -1;
    private static boolean left = false;

    public static void main(String args[]){
        /* Sample Input Array */
        //int[] input_array = new int[]{3,1,2,1};
        int[] input_array = new int[]{3,5,4,2,1,2,3,1};
        //int[] input_array = new int[]{1,2,3,2,4,4};
        /* end sample input */

        for(int i=0; i<input_array.length; i++){
            if(nodes.size() == 0){
                /* tree is empty, add root */
                BSTNode node = new BSTNode(input_array[i]);
                nodes.add(node);
            }else{
                /* search if node already exists */
                if(!contains(input_array[i])){
                    BSTNode node = new BSTNode(input_array[i]);
                    nodes.add(node);
                    nodes.get(parent).setChild(nodes.size()-1, left);
                }else{
                    System.out.println(input_array[i] + " : already exists - ignoring");
                }
            }
        }

        /* final print */
        System.out.print("Inorder Traversal: ");
        inOrderTraverse(nodes.get(0));

        System.out.println("");

        System.out.print("PostOrder Traversal: ");
        postOrderTraverse(nodes.get(0));

        System.out.println("");

        System.out.print("PreOrder Traversal: ");
        preOrderTraverse(nodes.get(0));

        System.out.println("");
    }

    private static boolean contains(int value){
        int index = 0;
        while(index >= 0){
            if (nodes.get(index).getValue() == value){
                return true;
            }
            if (nodes.get(index).getValue() > value){
                parent = index;
                left = true;
                index = nodes.get(index).getChild(true);
            }else{
                parent = index;
                left = false;
                index = nodes.get(index).getChild(false);
            }
        }
        return false;
    }

    private static void inOrderTraverse(BSTNode node){
        if(node == null){
            return;
        }
        if(node.getChild(true) != -1){
            inOrderTraverse(nodes.get(node.getChild(true)));
        }
        System.out.print(node.getValue() + " ");
        if(node.getChild(false) != -1){
            inOrderTraverse(nodes.get(node.getChild(false)));
        }
    }

    private static void postOrderTraverse(BSTNode node){
        if(node == null){
            return;
        }
        if(node.getChild(true) != -1){
            postOrderTraverse(nodes.get(node.getChild(true)));
        }
        if(node.getChild(false) != -1){
            postOrderTraverse(nodes.get(node.getChild(false)));
        }
        System.out.print(node.getValue() + " ");
    }

    private static void preOrderTraverse(BSTNode node){
        if(node == null){
            return;
        }
        System.out.print(node.getValue() + " ");
        if(node.getChild(true) != -1){
            preOrderTraverse(nodes.get(node.getChild(true)));
        }
        if(node.getChild(false) != -1){
            preOrderTraverse(nodes.get(node.getChild(false)));
        }
    }
}

Output:

2 : already exists – ignoring

3 : already exists – ignoring

1 : already exists – ignoring

Inorder Traversal: 1 2 3 4 5

PostOrder Traversal: 1 2 4 5 3

PreOrder Traversal: 3 2 1 5 4