Java : Print n-Tree level by level

10 Sep

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)
About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: