Amazon Interview Question Software Engineer / Developers
For the bst with input in the order { 14, 32, 16, 11, 4, 21, 19, 68, 65, 26 }, it is giving output as <14 11 32 4 68 16 65 21 26 19 >, which is wrong. this is not correct solution
Wrong solution. Give the input 14, 32, 16, 11, 4, 21, 19, 68, 65, 26, 31. See the output, it is 14 11 32 4 68 16 65 21 26 19 31, which is wrong.
Surely use 2 stacks:
......a.........
....b....c.......
..d...e...f...g..
.h.i.j.k.l.m.n.o.
1.push a
while !1.empty
1.pop a set flag=right
get a->right c 2.push c
a->left b 2.push b
this time stack is empty so set flag=left
2.pop b,c to 1
while !1.empty
1.pop b
b->left d 2.push d
b->right e 2.push e
1.pop c
c->left f 2.push f
c->right g 2.push g
1 is empty so set flag to right
2.pop g,f,e,d to 1
loop ... ...
To do a bfs, you use a queue. And to print elements of the odd level, you use a stack. What part of this more straightforward solution didn't you get?
It is not even clear what the two stacks 'solution' is and if it even works.
int heightTree (node *root) {
int lh, rh;
if (root == NULL)
return 0 ;
lh = heightTree(root->left) ;
rh = heightTree(root->right) ;
return (lh>rh?lh:rh)+1 ;
}
void printZigzagOrder (node *root) {
int height = heightTree(root) ;
stack<node*> s1, s2 ;
node* topEle ;
s1.push (root) ;
for ( int i = 0 ; i < height ; i ++ ) {
if (i%2 == 0) /* Use s1 */ {
printf ( "\n") ;
while (!s1.empty()) {
topEle = s1.top () ;
s1.pop () ;
printf ( "%d ", topEle->data) ;
if ( topEle->left )
s2.push (topEle->left) ;
if ( topEle->right )
s2.push (topEle->right) ;
}
} else { /* Use s2 */
printf ( "\n") ;
while (!s2.empty()) {
topEle = s2.top () ;
s2.pop () ;
printf ( "%d ", topEle->data) ;
if ( topEle->right )
s1.push (topEle->right) ;
if ( topEle->left )
s1.push (topEle->left) ;
}
}
}
}
We just require one stack, a bool and an int
1) Initially, bool = LEFT. Push root to stack.numNodesInLevel=1;
2) while(stack not empty)
{
if(bool == LEFT)
{
pop(); // & print
push(node->right);
push(node->left);
}
else if(bool == RIGHT)
{
pop(); // & print
push(node->left);
push(node->right);
}
if(LastNodeInLevel())
SwapBoolValue();
else
numNodesInLevel++;
}
3) bool LastNodeInLevel()
{
if((numNodesInLevel--) == 0)
return true;
else
return false;
}
This is not correct. This would fail miserably starting from level 3.
1
23
4567
by the time you push, so you push 1, then pop it, push 3 then 2, pop 2, and push 4,5... by that time stack 5 would be on top of stack, next time you pop, you get 5.
You must use 2 data structures. Either 2 stacks or one stack, one queue.
package findanagrams;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
class TreeNode{
int data;
TreeNode left,right;
TreeNode(int data) {
this.data = data;
left = null;
right = null;
}
@Override
public boolean equals(Object n) {
return (this.data == ((TreeNode)n).data);
}
}
public class Graph_Traverse {
private static final TreeNode EMPTY = new TreeNode(-1);
private TreeNode head;
public Graph_Traverse() {
this.head = createTree();
}
private TreeNode createTree(){
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
TreeNode n6 = new TreeNode(6);
TreeNode n7 = new TreeNode(7);
TreeNode n8 = new TreeNode(8);
TreeNode n9 = new TreeNode(9);
TreeNode n10 = new TreeNode(10);
TreeNode n11 = new TreeNode(11);
TreeNode n12 = new TreeNode(12);
TreeNode n13 = new TreeNode(13);
TreeNode n14 = new TreeNode(14);
TreeNode n15 = new TreeNode(15);
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
n3.left = n6;
n3.right = n7;
n4.left = n8;
n4.right = n9;
n5.left = n10;
n5.right = n11;
n6.left = n12;
n6.left = n13;
n7.left = n14;
n7.right = n15;
return n1;
}
public void PrintLevelOrder() {
boolean forward = true;
Queue<TreeNode> q = new LinkedList<TreeNode>();
Stack<TreeNode> s = new Stack<TreeNode>();
q.add(this.head);
q.add(EMPTY);
while (!q.isEmpty()) {
TreeNode g = q.remove();
if (g.left != null) {
q.add(g.left);
}
if(g.right!=null){
q.add(g.right);
}
if (g.equals(EMPTY)) {
if(!q.isEmpty()){
q.add(EMPTY);}
forward = !forward;
while (!s.isEmpty()) {
System.out.print(s.pop().data + " ");
}
continue;
}
if (forward == true) {
System.out.print(g.data + " ");
} else {
s.push(g);
}
}
}
public static void main(String[] args) {
Graph_Traverse graph_Traverse = new Graph_Traverse();
graph_Traverse.PrintLevelOrder();
}
}
this can be solved using a variant solution of level order traversal.
do the ordinary level order traversal ( using BFS indeed ).
if the height is odd (assuming root h =0 ) then print the level members in reverse (you can temporary store the level members).
else if even print normally.
O(n) time ( O(2^h) space if saving temporarily )
... hope it helps
agree with Amazaon EC with a minor difference. since only the odd layers are printed reversely, only the odd layer nodes should be pushed in the stack for printing purpose. the even layer nodes will be printed as per normal. thus, when deque, check whether it is odd layer or even layer, if even layer, print as per normal and enque the children nodes, while if odd layer, push into the stack to reverse printing.
correct me if I am wrong
just go for pre/in/post order traversal, and make note of position(u may use 0/1 travel for left and right), compute the position is the array for that node, use gotoxy();
simple hai!!!
in O(n) time and O(max_height) space
public void ZigZagPrint(Node node) {
boolean LR = true;
Stack<Node> pStack = new Stack<Node>();
pStack.push(node);
ZigZag(pStack,LR);
}
public void ZigZag(Stack<Node> Parent,boolean LR){
Stack<Node> Child = new Stack<Node>();
if (Child.isEmpty() &&Parent.isEmpty())return;
while (!Parent.isEmpty()) {
Node temp = Parent.pop();
System.out.print(temp.data+" , ");
if (LR) {
if (temp.leftChild != null) Child.push(temp.leftChild);
if (temp.rightChild != null)Child.push(temp.rightChild);
} else {
if (temp.rightChild != null) Child.push(temp.rightChild);
if (temp.leftChild != null) Child.push(temp.leftChild);
}
}
Parent=Child;
System.out.println();
ZigZag( Parent, !LR);
}
this is the running solution
algoguru, are you a self proclaimed guru, because the solution you put in here says so, the solution really sucks! The solution mentioned in the begining are the way to go for it. Using bfs and Q, thats it. algoguru, just go through these solution to make your life easier and don't post craps like you did.
I was asked the question in interview and I gave the right solution.
You need to create an Array of Double linked list.
Each element of Array points to Doubly linked list for a particular level.
While printing, we need to switch between levels(i.e for level 1, we print from start to end and for level 2, we print from end to start).
We need to start from head of tree. Add head to Array[0].
For for each level, look at the linked list in previous level. Add the children of previous level from left to right.
#include <stdio.h>
#include <stdlib.h>
#define DIRECTION_LEFT 1
#define DIRECTION_RIGHT 2
struct node {
int value;
struct node* left;
struct node* right;
};
typedef struct node * Node;
struct stack_node {
Node value;
struct stack_node * next;
};
typedef struct stack_node * StackNode;
StackNode createStackNode(Node value) {
StackNode node = (StackNode) malloc(sizeof(struct stack_node));
node->value = value;
node->next = NULL;
return node;
}
int isEmptyStack(StackNode stack) {
if (stack == NULL)
return 1;
return 0;
}
void push(StackNode * stack, Node value) {
StackNode node = createStackNode(value);
if (!isEmptyStack(*stack))
node->next = *stack;
*stack = node;
}
Node pop(StackNode * stack) {
if (isEmptyStack(*stack))
return NULL;
StackNode node = *stack;
*stack = (*stack)->next;
return node->value;
}
Node createNode(int value) {
Node node = (Node) malloc(sizeof(struct node));
node->value = value;
node->left = NULL;
node->right = NULL;
return node;
}
void insertNode(Node * root, int value) {
if (*root == NULL) {
*root = createNode(value);
return;
}
if (value <= (*root)->value)
insertNode(&((*root)->left), value);
else
insertNode(&((*root)->right), value);
}
void printInOrder(Node root) {
if (root != NULL) {
printInOrder(root->left);
printf("%d\t", root->value);
printInOrder(root->right);
}
}
void printPreOrder(Node root) {
if (root != NULL) {
printf("%d\t", root->value);
printPreOrder(root->left);
printPreOrder(root->right);
}
}
void printPostOrder(Node root) {
if (root != NULL) {
printPostOrder(root->left);
printPostOrder(root->right);
printf("%d\t", root->value);
}
}
void printZigZag(StackNode * stack, int direction) {
StackNode nextLevelStack = NULL;
while (!isEmptyStack(*stack)) {
Node node = pop(stack);
printf("%d\t", node->value);
if (direction == DIRECTION_LEFT) {
if(node->right!=NULL)
push(&nextLevelStack, node->right);
if(node->left!=NULL)
push(&nextLevelStack, node->left);
} else {
if(node->left!=NULL)
push(&nextLevelStack, node->left);
if(node->right!=NULL)
push(&nextLevelStack, node->right);
}
}
if(!isEmptyStack(nextLevelStack)) {
if(direction == DIRECTION_LEFT)
direction = DIRECTION_RIGHT;
else
direction = DIRECTION_LEFT;
printZigZag(&nextLevelStack,direction);
}
}
int main(void) {
Node root = NULL;
StackNode stack = NULL;
insertNode(&root, 8);
insertNode(&root, 3);
insertNode(&root, 10);
insertNode(&root, 1);
insertNode(&root, 6);
insertNode(&root, 14);
insertNode(&root, 4);
insertNode(&root, 7);
insertNode(&root, 13);
printf("\nIn-Order Traversal: ");
printInOrder(root);
printf("\nPre-Order Traversal: ");
printPreOrder(root);
printf("\nPost-Order Traversal: ");
printPostOrder(root);
printf("\nZig-Zag-Order Traversal: ");
push(&stack,root);
printZigZag(&stack,DIRECTION_LEFT);
return 0;
}
void zig_zag(struct tree* root)
{
deque<struct tree*> dq;
struct tree* curr;
dq.push_back(root);
bool flag=1,num1=0; // flag=1 signifies start from front and flag=0 signifies start from end.
int cnt1=1,cnt=0;
while(!dq.empty())
{
cnt1--;
if(flag==1)
{
//cout<<"f1*";
curr=dq.front();
dq.pop_front();
cout<<curr->data<<"->";
if(cnt1==0)
num1=1;
if(curr->left!=NULL)
{
cnt++;
dq.push_back(curr->left);
}
if(curr->right!=NULL)
{
cnt++;
dq.push_back(curr->right);
}
if(num1==1)
{
if(flag==1)
flag=0;
else
flag=1;
num1=0;
cnt1=cnt;
cnt=0;
}
}
else if(flag==0)
{
//cout<<"f0*";
curr=dq.back();
dq.pop_back();
cout<<curr->data<<"->";
if(cnt1==0)
num1=1;
if(curr->right!=NULL)
{
cnt++;
dq.push_front(curr->right);
}
if(curr->left!=NULL)
{
cnt++;
dq.push_front(curr->left);
}
if(num1==1)
{
if(flag==1)
flag=0;
else
flag=1;
num1=0;
cnt1=cnt;
cnt=0;
}
}
}
cout<<"END\n";
}
Solution without using stack
Tree's level is either even or odd, using this we can solve
Working code
#include<stdio.h>
struct node{
int data;
struct node *left;
struct node *right;
};
static int initLevel;
int heightOfTree(struct node *root){
if(root == NULL)
{
return 0;
}
int lHeight = heightOfTree(root->left);
int rHeight = heightOfTree(root->right);
return (lHeight > rHeight)?lHeight+1:rHeight+1;
}
struct node* newNode(int data)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
void printLine(struct node* root, int level){
if(root == NULL)
return;
if(level == 1)
printf("%d ",root->data);
else if(level > 1){
if(level%2==0&&initLevel%2==0){
printLine(root->right,level-1);
printLine(root->left,level-1);
}
else{
printLine(root->left,level-1);
printLine(root->right,level-1);
}
}
}
main(){
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
root->right->right->right = newNode(10);
root->right->right->left = newNode(12);
root->right->right->right->right = newNode(11);
root->left->left->left = newNode(8);
root->left->left->left->left = newNode(9);
int height = heightOfTree(root);
int i;
int rtl = 0;
for(i=1;i<=height;i++){
initLevel = i;
printLine(root,i);
}
return;
}
private static void zigzag(Tree tree) {
if (tree == null) return;
Stack<Tree> s1 = new Stack<>();
Stack<Tree> s2 = new Stack<>();
s1.push(tree);
Stack<Tree> stFrom = s1;
Stack<Tree> stTo = s2;
boolean left = true;
while (!s1.isEmpty() || !s2.empty()) {
if (stFrom.isEmpty()) {
Stack<Tree> tmp = stFrom;
stFrom = stTo;
stTo = tmp;
left = !left;
continue;
}
Tree t = stFrom.pop();
System.out.println(t.value + ", ");
if (left) {
if (t.left != null) stTo.push(t.left);
if (t.right != null) stTo.push(t.right);
} else {
if (t.right != null) stTo.push(t.right);
if (t.left != null) stTo.push(t.left);
}
}
}
Here is my implementation in c++
#include <cstdlib>
#include <stdio.h>
#include <cstring>
#include <complex>
#include <vector>
#include <cmath>
#include <ctime>
#include <iostream>
#include <numeric>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <iomanip>
#include <utility>
#include <locale>
#include <sstream>
#include <string> // this should be already included in <sstream>
#define FOR(i,n) for(i=0;i<n;i++)
#define FORI(i,a,n) for(i=a;i<n;i++)
#define FORC(it,C) for(it=C.begin();it!=C.end();it++)
#define scanI(x) scanf("%d",&x)
#define scanD(x) scanf("%lf",&x)
#define print(x) printf("%d\n",x)
#define ll long long
#define number32 4294967296ull
#define MAX 100001
///cout<<(double)(clock() - tStart)/CLOCKS_PER_SEC<<endl;
///clock_t tStart = clock();
using namespace std;
struct treeNode
{
struct treeNode *left;
int data;
struct treeNode *right;
};
typedef struct treeNode TreeNode;
typedef TreeNode *TreeNodePtr;
void insertNode(TreeNodePtr *treePtr,int value)
{
if(*treePtr== NULL)
{
*treePtr=(TreeNodePtr)malloc(sizeof(TreeNode));
if(*treePtr != NULL)
{
(*treePtr)->data=value;
(*treePtr)->left=NULL;
(*treePtr)->right=NULL;
}
else
{
// cout<<"Memory is not available "<<endl;
}
}
else
{
if(value<(*treePtr)->data)
{
insertNode(&((*treePtr)->left),value);
}
if(value>=(*treePtr)->data)
{
insertNode(&((*treePtr)->right),value);
}
}
}
void Inorder( TreeNodePtr treePtr)
{
if(treePtr != NULL)
{
Inorder(treePtr->left);
printf("%d\n",treePtr->data);
Inorder(treePtr->right);
}
}
void zigzagOrder(TreeNodePtr treePtr)
{
stack<TreeNodePtr> s1,s2;
TreeNodePtr cur1,cur2;
s1.push(treePtr);
do
{
while(!s1.empty())
{
cur1=s1.top();
s1.pop();
cout<<cur1->data<<" "<<endl;
if(cur1->left!=NULL)
s2.push(cur1->left);
if(cur1->right!=NULL)
s2.push(cur1->right);
}
while(!s2.empty())
{
cur2=s2.top();
s2.pop();
cout<<cur2->data<<" "<<endl;
if(cur2->left!=NULL)
s1.push(cur2->right);
if(cur2->right!=NULL)
s1.push(cur2->left);
}
}
while(!s1.empty()||!s2.empty());
}
int main()
{
int t,i;
int n;
TreeNodePtr rootPtr=NULL;
//int k=5;
//cout<<k<<" "<<(k<<1)<<" "<<(k>>1)<<endl;
srand(clock());
cin>>n;
FOR(i,n)
{
cin>>t;
insertNode(&rootPtr,t);
}
//Inorder(rootPtr);
zigzagOrder(rootPtr);
//cout<<"success"<<endl;
return 0;
}
#include <stdio.h>
#include <string.h>
struct tree *newnode(int data);
void push(int **data);
struct list
{
int data;
struct list *next;
}*top, *currentlevel=NULL,*nextlevel=NULL;
struct tree
{
int data;
struct tree *left;
struct tree *right;
};
main()
{
struct tree *tree1=newnode(1);
tree1->left=newnode(2);
tree1->right=newnode(3);
tree1->left->left=newnode(4);
tree1->left->right=newnode(5);
tree1->right->left=newnode(6);
tree1->right->right=newnode(7);
tree1->left->left->left=newnode(8);
tree1->left->left->right=newnode(9);
tree1->left->right->left=newnode(10);
tree1->left->right->right=newnode(11);
tree1->right->left->left=newnode(12);
tree1->right->left->right=newnode(13);
tree1->right->right->left=newnode(14);
tree1->right->right->right=newnode(15);
zigzag(tree1);
}
int zigzag(struct list *tree1)
{
int lefttoright=1;
push(tree1);
while(!isEmpty())
{
struct tree *tree3=pop();
printf(" %d",tree3->data);
if(lefttoright)
{
if(tree3->left!=0)
{
push1(tree3->left);
}
if(tree3->right!=0)
{
push1(tree3->right);
}
}
else
{
if(tree3->right!=0)
{
push1(tree3->right);
}
if(tree3->left!=0)
{
push1(tree3->left);
}
}
while(isEmpty())
{
lefttoright=1-lefttoright;
swap();
}
}
}
void swap()
{
currentlevel=nextlevel;
nextlevel=NULL;
}
int pop()
{
struct list *ptr;
ptr=currentlevel->data;
if(currentlevel==NULL)
{
printf(" overflow ");
}
currentlevel=currentlevel->next;
return ptr;
}
int isEmpty()
{
if(currentlevel==NULL)
{
return 1;
}
else
{
return 0;
}
}
struct tree *newnode(int data)
{
struct tree *tree3;
tree3=(struct tree *)malloc(sizeof(struct tree));
tree3->data=data;
tree3->left=NULL;
tree3->right=NULL;
return tree3;
}
void push(int **data)
{
struct list *p1=(struct list *)malloc(sizeof(struct list));
p1->data=data;
if(currentlevel==NULL)
{
p1->next=NULL;
currentlevel=p1;
}
else
{
p1->next=currentlevel;
currentlevel=p1;
}
}
void push1(int **data)
{
struct list *p11=(struct list *)malloc(sizeof(struct list));
p11->data=data;
if(nextlevel==NULL)
{
p11->next=NULL;
nextlevel=p11;
}
else
{
p11->next=nextlevel;
nextlevel=p11;
}
}
void CBinaryTree::PrintZigZag(Node* pNode)
{
static bool toggle = false;
if (pNode == NULL)
return;
pNode->DisplayId();
if ( toggle == false)
{
if (pNode->_pRight)
_NodeStack.push(pNode->_pRight);
if (pNode->_pLeft)
_NodeStack.push(pNode->_pLeft);
}
else
{
if (pNode->_pLeft)
_NodeStack.push(pNode->_pLeft);
if (pNode->_pRight)
_NodeStack.push(pNode->_pRight);
}
if (_NodeQueue.empty())
{
cout << endl;
if (toggle == false)
toggle = true;
else
toggle = false;
while(!_NodeStack.empty())
{
_NodeQueue.push(_NodeStack.top());
_NodeStack.pop();
}
}
Node* pNodeNext = NULL;
if( !_NodeQueue.empty())
{
pNodeNext = _NodeQueue.front();
_NodeQueue.pop();
PrintZigZag(pNodeNext);
}
}
Guys, please do not expect the binary tree as balanced and height logic would not be accurate for them.
public static void ZigZagTraverser(Node root)
{
Stack<Node> stk_LR = new Stack<Node>();
Stack<Node> stk_RL = new Stack<Node>();
stk_RL.push(root);
Node temp = null;
while(!(stk_LR.isEmpty() && stk_RL.isEmpty()))
{
if(!stk_LR.isEmpty())
{
temp = stk_LR.pop();
System.out.print(temp.getValue()+"\t");
if(temp.getRight()!=null)
{
stk_RL.push(temp.getRight());
}
if(temp.getLeft()!=null)
{
stk_RL.push(temp.getLeft());
}
}
else if(!stk_RL.isEmpty())
{
temp = stk_RL.pop();
System.out.print(temp.getValue()+"\t");
if(temp.getLeft()!=null)
{
stk_LR.push(temp.getLeft());
}
if(temp.getRight()!=null)
{
stk_LR.push(temp.getRight());
}
}
}
}
#include<stdio.h>
#include<stdlib.h>
struct node
{
int value;
struct node *left;
struct node *right;
};
void insert(struct node **temp,int key)
{
struct node *temp1=NULL;
if(*temp==NULL)
{
temp1=(struct node*)malloc(sizeof(struct node));
temp1->right=NULL;
temp1->left=NULL;
temp1->value=key;
*temp=temp1;
return;
}
if(((*temp)->value)<key)
{
insert(&(*temp)->right,key);
}
else if(((*temp)->value)>key)
{
insert(&(*temp)->left,key);
}
}
void preorder(struct node *temp)
{
if(temp!=NULL)
{
printf("%d\n",temp->value);
preorder(temp->left);
preorder(temp->right);
}
}
void print_zigzag(struct node *root)
{
int h=height(root);
int i,c=1;
for(i=1;i<h+1;i++)
{
c++;
zigzagorder(root,i,c);
}
}
void zigzagorder(struct node *root,int level,int c)
{
if(root==NULL)
return ;
if(level==1)
{
printf("%d\n",root->value);
}
else
{
if(c%2==0)
{
zigzagorder(root->left,level-1,c);
zigzagorder(root->right,level-1,c);
}
else
{
zigzagorder(root->right,level-1,c);
zigzagorder(root->left,level-1,c);
}
}
}
int height(struct node *node)
{
if (node==NULL)
return 0;
else
{
/* compute the height of each subtree */
int lheight = height(node->left);
int rheight = height(node->right);
/* use the larger one */
if (lheight > rheight)
return(lheight+1);
else return(rheight+1);
}
}
main()
{
struct node *root;
root=NULL;
printf("tree\n");
insert(&root,5);
insert(&root,10);
insert(&root,7);
//insert(&root,8);
insert(&root,3);
insert(&root,11);
insert(&root,2);
insert(&root,4);
insert(&root,1);
insert(&root,12);
//insert(&root,6);
printf("preorder:\n");
preorder(root);
printf("depth of tree is %d\n",height(root));
printf("print_zigzag:\n");
print_zigzag(root);
}
public void ZigZagTraversal(TreeNode root)
{
if (null == root)
{
Console.WriteLine("Binary Tree Empty.");
return;
}
Stack<TreeNode> oddLevel = new Stack<TreeNode>();
Stack<TreeNode> evenLevel = new Stack<TreeNode>();
TreeNode current = null;
oddLevel.Push(root);
while (oddLevel.Count > 0 || evenLevel.Count > 0)
{
while (oddLevel.Count > 0)
{
current = oddLevel.Pop();
Console.Write("\t" + current.Data);
if (current.Left != null)
{
evenLevel.Push(current.Left);
}
if (current.Right != null)
{
evenLevel.Push(current.Right);
}
}
while (evenLevel.Count > 0)
{
current = evenLevel.Pop();
Console.Write("\t" + current.Data);
if (current.Right != null)
{
oddLevel.Push(current.Right);
}
if (current.Left != null)
{
oddLevel.Push(current.Left);
}
}
}
}
private static void SpiralTraversal(Node root)
{
Stack<Node> stack1 = new Stack<Node>();
Stack<Node> stack2 = new Stack<Node>();
stack1.Push(root);
while (stack1.Count != 0 || stack2.Count != 0)
{
while (stack1.Count > 0)
{
Node curr = stack1.Pop();
if (curr.left != null)
stack2.Push(curr.left);
if (curr.right != null)
stack2.Push(curr.right);
Console.Write(curr.data + " ");
}
Console.WriteLine();
while (stack2.Count > 0)
{
Node curr = stack2.Pop();
if (curr.right != null)
stack1.Push(curr.right);
if (curr.left != null)
stack1.Push(curr.left);
Console.Write(curr.data + " ");
}
Console.WriteLine();
}
}
ZigZagOrder(struct node* root)
{
struct node* stack[15];
int i=0,j=1,k=-1,level_change=1,count=0,kIncrement=-1;
stack[++k]=root;
while(1)
{
j=j-1;
if(level_change==1)
{
if(stack[j]->right!=NULL)
{
stack[++k]=stack[j]->right;
count++;
}
if(stack[j]->left!=NULL)
{
stack[++k]=stack[j]->left;
count++;
}
}
else
{
if(stack[j]->left!=NULL)
{
stack[++k]=stack[j]->left;
count++;
}
if(stack[j]->right!=NULL)
{
stack[++k]=stack[j]->right;
count++;
}
}
if(i==j)
{
if(count==0)
break;
kIncrement=k;
j=k+1;
i=j-count;
count=0;
level_change=level_change*-1;
}
}
printf("\n");
for(i=0;i<k+1;i++)
printf("%d ",stack[i]->data);
}
public static void zigZagPrint(solution.Node root){
if(root==null) return;
boolean fromLeftToRight = false;
Stack<Node> s1 = new Stack<solution.Node>();
Stack<solution.Node> s2 = new Stack<solution.Node>();
s1.push(root);
while(!s1.isEmpty() || !s2.isEmpty()){
solution.Node temp = s1.peek();
s1.pop();
System.out.print(temp.value+" ");
if(fromLeftToRight){
if(temp.right!=null) s2.push(temp.right);
if(temp.left!=null)s2.push(temp.left);
}
else{
if(temp.left!=null)s2.push(temp.left);
if(temp.right!=null)s2.push(temp.right);
}
if(s1.isEmpty()){
s1=s2;
s2= new Stack<solution.Node>();
fromLeftToRight=!fromLeftToRight;
}
}
}
public static void zigZagPrint(solution.Node root){
if(root==null) return;
boolean fromLeftToRight = false;
Stack<Node> s1 = new Stack<solution.Node>();
Stack<solution.Node> s2 = new Stack<solution.Node>();
s1.push(root);
while(!s1.isEmpty() || !s2.isEmpty()){
solution.Node temp = s1.peek();
s1.pop();
System.out.print(temp.value+" ");
if(fromLeftToRight){
if(temp.right!=null) s2.push(temp.right);
if(temp.left!=null)s2.push(temp.left);
}
else{
if(temp.left!=null)s2.push(temp.left);
if(temp.right!=null)s2.push(temp.right);
}
if(s1.isEmpty()){
s1=s2;
s2= new Stack<solution.Node>();
fromLeftToRight=!fromLeftToRight;
}
}
}
solution.Node is my packaged Node class.
Essentially a typical Treenode
public static void zigZagPrint(solution.Node root){
if(root==null) return;
boolean fromLeftToRight = false;
Stack<Node> s1 = new Stack<solution.Node>();
Stack<solution.Node> s2 = new Stack<solution.Node>();
s1.push(root);
while(!s1.isEmpty() || !s2.isEmpty()){
solution.Node temp = s1.peek();
s1.pop();
System.out.print(temp.value+" ");
if(fromLeftToRight){
if(temp.right!=null) s2.push(temp.right);
if(temp.left!=null)s2.push(temp.left);
}
else{
if(temp.left!=null)s2.push(temp.left);
if(temp.right!=null)s2.push(temp.right);
}
if(s1.isEmpty()){
s1=s2;
s2= new Stack<solution.Node>();
fromLeftToRight=!fromLeftToRight;
}
}
}
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class TreeZigZagPrinter {
public static void main(String[] args) {
TreeNode a = new TreeNode('a');
TreeNode b = new TreeNode('b');
TreeNode c = new TreeNode('c');
TreeNode d = new TreeNode('d');
TreeNode e = new TreeNode('e');
TreeNode f = new TreeNode('f');
TreeNode g = new TreeNode('g');
TreeNode h = new TreeNode('h');
TreeNode i = new TreeNode('i');
TreeNode j = new TreeNode('j');
TreeNode k = new TreeNode('k');
TreeNode l = new TreeNode('l');
TreeNode m = new TreeNode('m');
TreeNode n = new TreeNode('n');
TreeNode o = new TreeNode('o');
a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.left = f;
c.right = g;
d.left = h;
d.right = i;
e.left = j;
e.right = k;
f.left = l;
f.right = m;
g.left = n;
g.right = o;
TreeZigZagPrinter tzz = new TreeZigZagPrinter();
tzz.root = a;
tzz.printTree();
}
TreeNode root;
Queue<TreeNode> q = new LinkedList<TreeNode>();
Stack<TreeNode> s = new Stack<TreeNode>();
boolean rightToLeft = false;
public void printTree() {
if (root == null) {
return;
}
rightToLeft = true;
q.add(root);
int nc = 1;
while (!q.isEmpty()) {
// reverse elements in Queue
while (!q.isEmpty()) {
s.push(q.remove());
}
while (!s.isEmpty()) {
q.add(s.pop());
}
int c = nc;
nc = 0;
// System.out.println("nodes to pop: " + nc);
while (c > 0) {
c--;
TreeNode x = q.remove();
// System.out.println("pop to add children: " + x);
if (rightToLeft) {
if (x.right != null) {
q.add(x.right);
// System.out.println("child added: " + x.right);
nc++;
}
if (x.left != null) {
q.add(x.left);
// System.out.println("child added: " + x.left);
nc++;
}
} else {
if (x.left != null) {
q.add(x.left);
nc++;
}
if (x.right != null) {
q.add(x.right);
nc++;
}
}
s.push(x);
}
rightToLeft = !rightToLeft;
while (!s.isEmpty()) {
System.out.print(s.pop().val);
System.out.print(" ");
}
// nc *= 2;
}
}
}
class TreeNode {
@Override
public String toString() {
return val + "";
}
public TreeNode(char val) {
super();
this.val = val;
}
TreeNode right;
TreeNode left;
char val;
}
import java.util.Stack;
/**
* Given the following Binary Tree.
* <p>
* 6
* / \
* 3 4
* / \ \
* 5 1 0
* / \ / \
* 9 2 8 25
* / \ / \
* 11 70 30 36
* <p>
* Sample Output -
* <p>
* 6 -> 4 -> 3 -> 5 -> 1 -> 0 -> 8 -> 2 ->9 -> 7
*/
public class BinaryTreePrintZigZag {
private static class Node {
Node left;
Node right;
int value;
public Node(int value) {
this.value = value;
}
public String toString() {
return Integer.toString(value);
}
}
public static void main(String[] args) {
Node root = new Node(6);
root.left = new Node(3);
root.right = new Node(4);
root.left.left = new Node(5);
root.left.right = new Node(1);
root.left.left.left = new Node(9);
root.left.left.right = new Node(2);
root.right.right = new Node(0);
root.right.right.right = new Node(25);
root.right.right.left = new Node(8);
root.left.left.left.right = new Node(7);
root.left.left.left.left = new Node(11);
root.left.left.left.right = new Node(70);
root.right.right.left.left = new Node(30);
root.right.right.left.right = new Node(36);
printZigZag(root);
}
public static void printZigZag(Node root) {
if (root == null) return;
Stack<Node> thisStack = new Stack<>(), thatStack = new Stack<>();
thisStack.add(root);
Node leftTmp, rightTmp;
Node current;
int level = 0;
for (; ; ) {
while (!thisStack.isEmpty()) {
current = thisStack.pop();
System.out.print(current + " -> ");
leftTmp = (level % 2 == 0) ? current.right : current.left;
rightTmp = (level % 2 == 0) ? current.left : current.right;
if (leftTmp != null) thatStack.push(leftTmp);
if (rightTmp != null) thatStack.push(rightTmp);
}
level++;
if (thatStack.isEmpty()) break;
// Swap the Stack pointers.
Stack<Node> tmp = thisStack;
thisStack = thatStack;
thatStack = tmp;
}
}
}
Step1:Find Depth/Hieght of the tree
int maxDepth=tree.findHeightOfTree(root);
Step2:Iterate through all levels
for(int level=maxDepth;level>=1;level--){
tree.printTreeZigZag(root,1,level);
}
public int printTreeZigZag(Node root, int level1,int level2) {
if(root==null){
return 0;
}
if (level2 % 2 == 0) {
if (level1 == level2) {
System.out.print(root.data + " , ");
return 0;
} else {
printTreeZigZag(root.leftLink, level1 + 1, level2);
printTreeZigZag(root.rightLink, level1 + 1, level2);
}
return 1;
} else if(level2 % 2 == 1){
if (level1 == level2) {
System.out.print(root.data + " , ");
return 0;
} else {
printTreeZigZag(root.rightLink, level1 + 1, level2);
printTreeZigZag(root.leftLink, level1 + 1, level2);
}
}
return 0;
}
public class TraverseTreeInZigZag {
class Node{
int value;
}
public static Node qHead;
public static Node qTail;
public static Node stackHead;
public static Node stackTail;
void traverse(Node node){
q.enq(node);
System.out.println(node.value);
int count = 0;
while(!(q.isEmpty && stack.isEmpty)){
while(!q.isEmpty()){
Node node = q.deq();
System.out.println(node.value);
if(count % 2 != 0){
if(node.rightChild() != null){
stack.push(node.rightChild());
}
if(node.leftChild() != null){
stack.push(node.leftChild());
}
}else{
if(node.leftChild() != null){
stack.push(node.leftChild());
}
if(node.rightChild() != null){
stack.push(node.rightChild());
}
}
}
while(!stack.isEmpty()){
Node node = stack.pop();
q.enq(node);
}
count++;
}
}
}
class TreeNode {
TreeNode right;
TreeNode left;
char val;
public TreeNode(char val) {
super();
this.val = val;
}
@Override
public String toString() {
return val + "";
}
}
public class TreeZigZag2 {
private static void zigZagPrint(TreeNode root){
if(root==null) return;
Queue<TreeNode> s1 = new LinkedList<>();
Queue<TreeNode> s2 = new LinkedList<>();
Queue<TreeNode> s3 = new LinkedList<>();
s1.add(root);
s3.add(root);
while(!s1.isEmpty() || !s2.isEmpty()){
TreeNode temp = s1.peek();
s1.remove();
if(temp.left!=null) {s2.add(temp.left); s3.add(temp.left);}
if(temp.right!=null) {s2.add(temp.right); s3.add(temp.right);}
if(s1.isEmpty()){
s1=s2;
s2= new LinkedList<TreeNode>();
}
}
s3.forEach(System.out::print);
}
public static void main(String[] args) {
TreeNode a = new TreeNode('a');
TreeNode b = new TreeNode('b');
TreeNode c = new TreeNode('c');
TreeNode d = new TreeNode('d');
TreeNode e = new TreeNode('e');
TreeNode f = new TreeNode('f');
TreeNode g = new TreeNode('g');
TreeNode h = new TreeNode('h');
TreeNode i = new TreeNode('i');
TreeNode j = new TreeNode('j');
TreeNode k = new TreeNode('k');
TreeNode l = new TreeNode('l');
TreeNode m = new TreeNode('m');
TreeNode n = new TreeNode('n');
TreeNode o = new TreeNode('o');
TreeNode p = new TreeNode('p');
TreeNode q = new TreeNode('q');
TreeNode r = new TreeNode('r');
TreeNode s = new TreeNode('s');
TreeNode t = new TreeNode('t');
TreeNode u = new TreeNode('u');
TreeNode v = new TreeNode('v');
a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.left = f;
c.right = g;
d.left = h;
d.right = i;
e.left = j;
e.right = k;
f.left = l;
f.right = m;
g.left = n;
g.right = o;
h.right = p;
j.left = q;
k.left = r;
k.right = s;
l.left = t;
m.right = u;
n.left = v;
zigZagPrint(a);
}
class TreeNode {
TreeNode right;
TreeNode left;
char val;
public TreeNode(char val) {
super();
this.val = val;
}
@Override
public String toString() {
return val + "";
}
}
public class TreeZigZag2 {
private static void zigZagPrint(TreeNode root){
if(root==null) return;
Queue<TreeNode> s1 = new LinkedList<>();
Queue<TreeNode> s2 = new LinkedList<>();
Queue<TreeNode> s3 = new LinkedList<>();
s1.add(root);
s3.add(root);
while(!s1.isEmpty() || !s2.isEmpty()){
TreeNode temp = s1.peek();
s1.remove();
if(temp.left!=null) {s2.add(temp.left); s3.add(temp.left);}
if(temp.right!=null) {s2.add(temp.right); s3.add(temp.right);}
if(s1.isEmpty()){
s1=s2;
s2= new LinkedList<TreeNode>();
}
}
s3.forEach(System.out::print);
}
public static void main(String[] args) {
TreeNode a = new TreeNode('a');
TreeNode b = new TreeNode('b');
TreeNode c = new TreeNode('c');
TreeNode d = new TreeNode('d');
TreeNode e = new TreeNode('e');
TreeNode f = new TreeNode('f');
TreeNode g = new TreeNode('g');
TreeNode h = new TreeNode('h');
TreeNode i = new TreeNode('i');
TreeNode j = new TreeNode('j');
TreeNode k = new TreeNode('k');
TreeNode l = new TreeNode('l');
TreeNode m = new TreeNode('m');
TreeNode n = new TreeNode('n');
TreeNode o = new TreeNode('o');
TreeNode p = new TreeNode('p');
TreeNode q = new TreeNode('q');
TreeNode r = new TreeNode('r');
TreeNode s = new TreeNode('s');
TreeNode t = new TreeNode('t');
TreeNode u = new TreeNode('u');
TreeNode v = new TreeNode('v');
a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.left = f;
c.right = g;
d.left = h;
d.right = i;
e.left = j;
e.right = k;
f.left = l;
f.right = m;
g.left = n;
g.right = o;
h.right = p;
j.left = q;
k.left = r;
k.right = s;
l.left = t;
m.right = u;
n.left = v;
zigZagPrint(a);
}
class TreeNode {
TreeNode right;
TreeNode left;
char val;
public TreeNode(char val) {
super();
this.val = val;
}
@Override
public String toString() {
return val + "";
}
}
public class TreeZigZag2 {
private static void zigZagPrint(TreeNode root){
if(root==null) return;
Queue<TreeNode> s1 = new LinkedList<>();
Queue<TreeNode> s2 = new LinkedList<>();
Queue<TreeNode> s3 = new LinkedList<>();
s1.add(root);
s3.add(root);
while(!s1.isEmpty() || !s2.isEmpty()){
TreeNode temp = s1.peek();
s1.remove();
if(temp.left!=null) {s2.add(temp.left); s3.add(temp.left);}
if(temp.right!=null) {s2.add(temp.right); s3.add(temp.right);}
if(s1.isEmpty()){
s1=s2;
s2= new LinkedList<TreeNode>();
}
}
s3.forEach(System.out::print);
}
public static void main(String[] args) {
TreeNode a = new TreeNode('a');
TreeNode b = new TreeNode('b');
TreeNode c = new TreeNode('c');
TreeNode d = new TreeNode('d');
TreeNode e = new TreeNode('e');
TreeNode f = new TreeNode('f');
TreeNode g = new TreeNode('g');
TreeNode h = new TreeNode('h');
TreeNode i = new TreeNode('i');
TreeNode j = new TreeNode('j');
TreeNode k = new TreeNode('k');
TreeNode l = new TreeNode('l');
TreeNode m = new TreeNode('m');
TreeNode n = new TreeNode('n');
TreeNode o = new TreeNode('o');
TreeNode p = new TreeNode('p');
TreeNode q = new TreeNode('q');
TreeNode r = new TreeNode('r');
TreeNode s = new TreeNode('s');
TreeNode t = new TreeNode('t');
TreeNode u = new TreeNode('u');
TreeNode v = new TreeNode('v');
a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.left = f;
c.right = g;
d.left = h;
d.right = i;
e.left = j;
e.right = k;
f.left = l;
f.right = m;
g.left = n;
g.right = o;
h.right = p;
j.left = q;
k.left = r;
k.right = s;
l.left = t;
m.right = u;
n.left = v;
zigZagPrint(a);
}
class TreeNode {
TreeNode right;
TreeNode left;
char val;
public TreeNode(char val) {
super();
this.val = val;
}
@Override
public String toString() {
return val + "";
}
}
public class TreeZigZag2 {
private static void zigZagPrint(TreeNode root){
if(root==null) return;
Queue<TreeNode> s1 = new LinkedList<>();
Queue<TreeNode> s2 = new LinkedList<>();
Queue<TreeNode> s3 = new LinkedList<>();
s1.add(root);
s3.add(root);
while(!s1.isEmpty() || !s2.isEmpty()){
TreeNode temp = s1.peek();
s1.remove();
if(temp.left!=null) {s2.add(temp.left); s3.add(temp.left);}
if(temp.right!=null) {s2.add(temp.right); s3.add(temp.right);}
if(s1.isEmpty()){
s1=s2;
s2= new LinkedList<TreeNode>();
}
}
s3.forEach(System.out::print);
}
public static void main(String[] args) {
TreeNode a = new TreeNode('a');
TreeNode b = new TreeNode('b');
TreeNode c = new TreeNode('c');
TreeNode d = new TreeNode('d');
TreeNode e = new TreeNode('e');
TreeNode f = new TreeNode('f');
TreeNode g = new TreeNode('g');
TreeNode h = new TreeNode('h');
TreeNode i = new TreeNode('i');
TreeNode j = new TreeNode('j');
TreeNode k = new TreeNode('k');
TreeNode l = new TreeNode('l');
TreeNode m = new TreeNode('m');
TreeNode n = new TreeNode('n');
TreeNode o = new TreeNode('o');
TreeNode p = new TreeNode('p');
TreeNode q = new TreeNode('q');
TreeNode r = new TreeNode('r');
TreeNode s = new TreeNode('s');
TreeNode t = new TreeNode('t');
TreeNode u = new TreeNode('u');
TreeNode v = new TreeNode('v');
a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.left = f;
c.right = g;
d.left = h;
d.right = i;
e.left = j;
e.right = k;
f.left = l;
f.right = m;
g.left = n;
g.right = o;
h.right = p;
j.left = q;
k.left = r;
k.right = s;
l.left = t;
m.right = u;
n.left = v;
zigZagPrint(a);
}
public static void printZigZag(BinaryTreeNode<Integer> node) {
Stack<BinaryTreeNode<Integer>> s1 = new Stack<BinaryTreeNode<Integer>>();
Stack<BinaryTreeNode<Integer>> s2 = new Stack<BinaryTreeNode<Integer>>();
s1.push(node);
boolean newLine = false;
while (!s1.empty() || !s2.empty()) {
if(newLine) {
System.out.println();
}
while (!s1.empty()) {
BinaryTreeNode<Integer> temp = s1.peek();
s1.pop();
System.out.print(temp.data + " ");
if (temp.left != null)
s2.push(temp.left);
if (temp.right != null)
s2.push(temp.right);
}
System.out.println();
while (!s2.empty()) {
BinaryTreeNode<Integer> temp = s2.peek();
s2.pop();
System.out.print(temp.data + " ");
if (temp.right != null)
s1.push(temp.right);
if (temp.left != null)
s1.push(temp.left);
}
newLine = true;
}
}
since it is layer-by-layer printing, so we can use queue, for breadth first. to implement zig-zag operation, we can use one stack. so I think the data structure would be a queue of stack, the same layer nodes will be in stack.
- Vir Pratap Uttam May 04, 2015private static void zigZagTraversal(BinaryTreeNode root) { int leftToRight=1; BinaryTreeNode temp; Stack<BinaryTreeNode> currentLevel=new Stack<BinaryTreeNode>(); Stack<BinaryTreeNode> nextLevel=new Stack<BinaryTreeNode>(); System.out.println("Zig Zag Traversal"); currentLevel.push(root); while (!currentLevel.isEmpty()) { temp = currentLevel.pop(); if(temp!=null) { System.out.println(temp.getData()); if(leftToRight==1) { if (temp.getLeft() != null) nextLevel.push(temp.getLeft()); if (temp.getRight() != null) nextLevel.push(temp.getRight()); } else { if (temp.getRight() != null) nextLevel.push(temp.getRight()); if (temp.getLeft() != null) nextLevel.push(temp.getLeft()); } } if(currentLevel.isEmpty()) { leftToRight=1-leftToRight; while(!nextLevel.isEmpty()) { currentLevel.push(nextLevel.pop()); } } } }