Amazon Interview Question
Software Engineer / DevelopersNo need to use additional stack. Just pass another parameter that shows the current level is even or odd. If it is even (the root is 0), starting from right child to enqueue all the children from the right; otherwise, starting from the left child to enqueue all the children from the left.
/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
void printTree(Node root){
//declare variables
Queue<Node> q = new LinkedList<Node>();
int currentLevel = 1;
int children = 0; // number of children of current level
int counter = 1; // number of pop in order to advance next level
q.push(root);
while(!q.isEmpty()){
Node e = q.pop();
System.out.print(e);
count--;
if(currentLevel %2 ==1){
if(e.left!=null){
q.add(e.left);
children++;
}
if(e.right!=null){
q.add(e.right);
children++;
}
}else{
if(e.left!=null){
q.add(e.left);
children++;
}
if(e.right!=null){
q.add(e.right);
children++;
}
}
if(count == 0){
count = children;
currentLevel ++;
children=0;
}
}
}
}
The following is the java code which is working..
public void printTreeZigZag(Node root){
Queue<Node> q = new LinkedList<Node>();
Stack<Node> nl = new Stack<Node>();
q.offer(root);
q.offer(null);
boolean flip=false;
while(!q.isEmpty()){
Node n = q.poll();
if(n!=null)
nl.push(n);
else{
while(!nl.empty()){
Node p = nl.pop();
System.out.print(p.getData()+"\t");
if(flip){
if(p.getRight()!=null)
q.offer(p.getRight());
if(p.getLeft()!=null)
q.offer(p.getLeft());
}else{
if(p.getLeft()!=null)
q.offer(p.getLeft());
if(p.getRight()!=null)
q.offer(p.getRight());
}
}
q.offer(null);
}
if(q.peek()==null){
flip=!flip;
}
}
}
The following is the java code which is working.. re-submiting just to keep the fomat
public void printTreeZigZag(Node root){
Queue<Node> q = new LinkedList<Node>();
Stack<Node> nl = new Stack<Node>();
q.offer(root);
q.offer(null);
boolean flip=false;
while(!q.isEmpty()){
Node n = q.poll();
if(n!=null)
nl.push(n);
else{
while(!nl.empty()){
Node p = nl.pop();
System.out.print(p.getData()+"\t");
if(flip){
if(p.getRight()!=null)
q.offer(p.getRight());
if(p.getLeft()!=null)
q.offer(p.getLeft());
}else{
if(p.getLeft()!=null)
q.offer(p.getLeft());
if(p.getRight()!=null)
q.offer(p.getRight());
}
}
q.offer(null);
}
if(q.peek()==null){
flip=!flip;
}
}
}
Small Correction to avoid the infinite loop
public void printTreeZigZag(Node root){
Queue<Node> q = new LinkedList<Node>();
Stack<Node> nl = new Stack<Node>();
q.offer(root);
q.offer(null);
boolean flip=false;
while(!q.isEmpty()){
Node n = q.poll();
if(n!=null)
nl.push(n);
else{
boolean fillnull=false;
while(!nl.empty()){
Node p = nl.pop();
System.out.print(p.getData()+"\t");
if(flip){
fillnull = true;
if(p.getRight()!=null)
q.offer(p.getRight());
if(p.getLeft()!=null)
q.offer(p.getLeft());
}else{
fillnull = true;
if(p.getLeft()!=null)
q.offer(p.getLeft());
if(p.getRight()!=null)
q.offer(p.getRight());
}
}
if(fillnull)
q.offer(null);
}
if(q.peek()==null){
flip=!flip;
}
}
}
First convert the Binary tree into array representation and then use array and stack to print the above pattern
Void printTree(Node root){
Node [] arrNode = new Node[N] // N is the number of nodes in tree
ArrNode[0] = root;
For(int I = 0; I < d; I++) {// d depth of binary tree
ArrNode[2*I + 1] = arr[0].leftPtr;
ArrNode[2*I + 2] = arr[0].rightPtr;
}
Int start Index = 0;
Int j = 0;
Stack stack = new Stack(N);
For(int I = 0; I < d; I++){
If(I == 1 || I % 2 != 0){
Start Index = j;
While( j < start Index + I powerOf 2){
Stack.push(arrNode[j])
J++;
}
While(start Index < j){
ArrNode[startIndex] = stack.pop();
StartIndex++;
}
}else{
J = j + I powerOf 2;
}
}
For(innt I=0; I < n; I++){
System.out.println(arrNode[i]);
}
}
This may be similar to Priyanka's answer. Covert the tree to a binary tree, then traverse it. At each level, the left-most or right-most node can be expressed as a function of height (starting at 1):
left-most-node(height) => 2 ^ (height - 1)
right-most-node(height) => (2 ^ height) - 1
Using this, a for loop can be coded as:
for(var i = 0, left-to-right = true; i < height; i++) {
left-end = 2 ^ (i - 1)
right-end = (2 ^ i) - 1
if(left-to-right) {
print array values from left-end to right-end
}
else {
print array values from right-end to left-end
}
}
public static void ZigZag_Traversal(Node root)
{
//uses two stack "even" and "odd" for storing even and odd members of the tree.
//tree starts with level 0 thats even. so keeps root in even stack
//when popping elements from even stack put its children in odd stack taken as left child pushed first and then right
//when popping elements from odd stack put its children in even stack taken as right child pushed first then left child.
//when current stack is empty process with next one and when both are empty stop.
Stack<Node> evenStack = new Stack<Node>();
Stack<Node> oddStack = new Stack<Node>();
Stack<Node> currStack;
Stack<Node> otherStack;
String level;
evenStack.push(root);
while((!evenStack.empty()) || (!oddStack.empty()))
{
if(!evenStack.empty())
{
currStack = evenStack;
otherStack = oddStack;
level = "even";
}
else
{
currStack = oddStack;
otherStack = evenStack;
level = "odd";
}
//start traversing the tree.
while(!currStack.empty())
{
if(level.equalsIgnoreCase("even"))
{
Node poppedNode = currStack.pop();
//print node value in order to print the tree in ZigZag manner.
System.out.print(poppedNode.value + ",");
//push it's children into otherStack taken from left child first then right child if not Null.
if(poppedNode.left != null)
{
otherStack.push(poppedNode.left);
}
if(poppedNode.right != null)
{
otherStack.push(poppedNode.right);
}
}
else
{
Node poppedNode = currStack.pop();
//print node value in order to print the tree in ZigZag manner.
System.out.print(poppedNode.value + ",");
//push it's children into otherStack taken from right child first then left child if not Null.
if(poppedNode.right != null)
{
otherStack.push(poppedNode.right);
}
if(poppedNode.left != null)
{
otherStack.push(poppedNode.left);
}
}
}//end of inner while
}
}
// writing the alogorithm here
print stack(int turn)
{
while stack[turn][i]!=null
{
pop and print;
if(turn==0)
{
push(stack[1], leftchildof(popped element));
push(stack[1], rightchildof(popped element));
}
if(turn==1)
{
push(stack[0], rightchildof(popped element));
push(stack[0], leftchildof(popped element));
}
if(turn==0)
turn=1;
else
turn=0;
if(stack[turn] not empty)
call(turn);
else
return
}
modification of level order display ...
- xyz May 26, 2010Do simple level order display with one queue, with the modification that,
1.whenever nullnode comes as a result of deque(or any other indicator u use for next level), dequeue all elements one by one and push in an stack. At the same time, enqueue the children. Now display all elems of stack and enqueue a null node in queue.