CareerCup

package com.datastructure.trees;

import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingDeque;

public class N_aryTreeNodeImpl {

	static int k = 3;

	public static void main(String[] args) {

		N_aryTreeNode root = createN_aryTree();
		zigZagTraversal(root, k);
	}

	private static void zigZagTraversal(N_aryTreeNode root, int k) {
		int leftToRight = 1;
		N_aryTreeNode temp;
		Queue<N_aryTreeNode> currentLevel = new LinkedBlockingDeque<N_aryTreeNode>();
		Stack<N_aryTreeNode> nextLevel = new Stack<N_aryTreeNode>();

		System.out.println("Zig Zag Traversal");
		currentLevel.add(root);
		while (!currentLevel.isEmpty()) {
			temp = currentLevel.poll();
			N_aryTreeNode[] childArr = temp.getChild();
			if (temp != null) {
				System.out.print(" " + temp.getData());
				if (leftToRight == 1) {
					for (int i = 0; i < k; i++) {
						if (childArr != null && childArr[i] != null)
							nextLevel.push(childArr[i]);
					}

				} else {
					for (int i = k - 1; i >= 0; i--) {
						if (childArr != null && childArr[i] != null)
							nextLevel.push(childArr[i]);
					}

				}
			}

			if (currentLevel.isEmpty()) {
				leftToRight = 1 - leftToRight;
				while (!nextLevel.isEmpty()) {
					currentLevel.add(nextLevel.pop());
				}
			}
		}
	}

	private static N_aryTreeNode createN_aryTree() {
		N_aryTreeNode node1 = new N_aryTreeNode(k);
		N_aryTreeNode node2 = new N_aryTreeNode(k);
		N_aryTreeNode node3 = new N_aryTreeNode(k);
		N_aryTreeNode node4 = new N_aryTreeNode(k);
		N_aryTreeNode node5 = new N_aryTreeNode(k);
		N_aryTreeNode node6 = new N_aryTreeNode(k);
		N_aryTreeNode node7 = new N_aryTreeNode(k);
		N_aryTreeNode node8 = new N_aryTreeNode(k);
		N_aryTreeNode node9 = new N_aryTreeNode(k);
		N_aryTreeNode node10 = new N_aryTreeNode(k);

		node5.setData(5);

		node1.setData(1);
		N_aryTreeNode[] childNode1 = { node2, node6, node10 };
		node1.setChild(childNode1);

		node2.setData(2);
		N_aryTreeNode[] childNode2 = { node3, node4, node5 };
		node2.setChild(childNode2);

		node6.setData(6);
		N_aryTreeNode[] childNode6 = { node7, node8, node9 };
		node6.setChild(childNode6);

		node3.setData(3);
		node3.setChild(null);

		node4.setData(4);
		node4.setChild(null);

		node5.setData(5);
		node5.setChild(null);

		node7.setData(7);
		node7.setChild(null);
		node8.setData(8);
		node8.setChild(null);
		node9.setData(9);
		node9.setChild(null);
		node10.setData(10);
		node10.setChild(null);
		return node1;
	}

}

{struct node
{
int value;
struct node* child[5];
};
int n = 5;//maximum number of child nodes

void zigzag(struct node * root)
{
if(root== NULL)
return;
Stack s1;
Stack s2;
int i =0;
s1.push(root)
while(!s1.empty() || !s2.empty())
{
while(!s1.empty())
{
root = s1.pop();
cout<<root->value;
for(i =0;i< n;i++)
if(root->child[i])
s2.push(root->child[i]);
}
if(s1.empty())
cout<<endl; // empty line after every level
while(!s2.empty())
{
root = s2.pop();
cout<<root->value;
for(i =n-1;i> 0;i--)
if(root->child[i])
s1.push(root->child[i])
}
if(s2.empty())
cout<<endl;//// empty line after every level

}


}

}

class static NaryTreeNode<T>{
    ArrayList<NaryTreeNode<T>> children;
    T value;
    
    public NaryTreeNode<T>(T value){
        this.children = new ArrayList<NaryTreeNode<T>>();
        this.value = value;
    }
}

public static void printZigZag(NaryTreeNode<String> node){
    Stack<NaryTreeNode<String>> thisLevel = new Stack<NaryTreeNode<String>>();
    Stack<NaryTreeNode<String>> nextLevel = new Stack<NaryTreeNode<String>>();
    Stack<NaryTreeNode<String>> temp;
    boolean isLeftToRight = false;
    StringBuilder line = new StringBuilder();

    thisLevel.push(node);
    while(!thisLevel.isEmpty()){
        while(!thisLevel.isEmpty()){
            node = thisLevel.pop();
            line.append(node.value);
            line.append(' ');
            if(isLeftToRight){
                for(int i = 0; i < node.children.size(); i++){
                    nextLevel.push(node.children.get(i));
                }
            }
            else{
                for(int i =  node.children.size() -1; i > -1; i--){
                    nextLevel.push(node.children.get(i);
                }
            }
       }
       java.lang.System.out.println(line.toString());
       line.setLength(0);
       temp = thisLevel;
       thisLevel = nextLevel;
       nextLevel = temp;
       isLeftToRight = !isLeftToRight;
    }
}