Amazon Interview Question
SDE1sTeam: Kindle
Country: India
Interview Type: Written Test
Traverse the tree using Breadth First approach.
On each level print the element, Print should be reversed on each level to have zigzag effect
take one stack and one queue.
push root into stack..
while(!stack.empty() || !queue.empty())
{
while (!stack.empty())
{
elem=stack.pop();
print elem.value;
queue.push(elem->left);
queue.push(elem->right);
}
while(!queue.empty())
{
elem=queue.pop();
print elem;
stack.push(elem->left);
stack.push(elem->right);
}
}
public static class TreeNode{
TreeNode left, right;
int val;
}
public static void printZigzag(TreeNode head){
if(head == null){
return;
}
boolean goRight = false;
LinkedList<TreeNode> list = new LinkedList<TreeNode>();
LinkedList<TreeNode> temp = new LinkedList<TreeNode>();
list.add(head);
StringBuilder lineBuilder = new StringBuilder();
TreeNode node = null;
//while there's still content
while(!list.isEmpty()){
//while there are still unprocessed TreeNodes for this line
while(!list.isEmpty()){
if(goRight){
node = list.removeFirst();
}
else{
node = list.removeLast();
}
lineBuilder.append(node.val);
lineBuilder.append(' ');
if(node.left != null){
temp.add(node.left);
}
if(node.right != null){
temp.add(node.right);
}
}
//make output and prep for next line
java.lang.System.out.println(lineBuilder.toString());
lineBuilder.setLength(0);
LinkedList<TreeNode> holder = list;
list = temp;
temp = holder;
goRight = !goRight;
}
}
typedef struct Node{
int value;
char type;
struct Node * left_child;
struct Node * right_child;
}Node;
Queue queue;
Stack stack;
void printZigZag(Node * head){
if(head == null){
return;
}
queue.push(head);
int row_number = 0;
int num_of_elements = 1;
int elements_covered_so_far = 0;
while(queue.size != 0){
Node * node = queue.pop();
if(node.type == PLACE_HOLDER){
continue;
}
elements_covered_so_far ++;
if(elements_covered_so_far == num_of_elements){
Node * place_holder = (Node*)malloc(sizeof(Node));
place_holder.type == PLACE_HOLDER;
queue.push(place_holder);
elements_covered_so_far = 0;
num_of_elements = num_of_elements * 2;
row_number++;
}
queue.push(node->left_child);
queue.push(node->right_child);
if(row_number % 2 ==1){
//print in reverse order
stack.push(node);
}
else{
printf("%d ",node->value);
}
if(stack.size() == num_of_elements){
while(!stack.is_empty()){
Node * node = stack.pop();
printf("%d ",node->value);
}
}
}
}
typedef struct Node{
int value;
char type;
struct Node * left_child;
struct Node * right_child;
}Node;
Queue queue;
Stack stack;
void printZigZag(Node * head){
if(head == null){
return;
}
queue.push(head);
int row_number = 0;
int num_of_elements = 1;
int elements_covered_so_far = 0;
while(queue.size != 0){
Node * node = queue.pop();
if(node.type == PLACE_HOLDER){
continue;
}
elements_covered_so_far ++;
if(elements_covered_so_far == num_of_elements){
Node * place_holder = (Node*)malloc(sizeof(Node));
place_holder.type == PLACE_HOLDER;
queue.push(place_holder);
elements_covered_so_far = 0;
num_of_elements = num_of_elements * 2;
row_number++;
}
queue.push(node->left_child);
queue.push(node->right_child);
if(row_number % 2 ==1){
//print in reverse order
stack.push(node);
}
else{
printf("%d ",node->value);
}
if(stack.size() == num_of_elements){
while(!stack.is_empty()){
Node * node = stack.pop();
printf("%d ",node->value);
}
}
}
}
typedef struct Node{
int value;
char type;
struct Node * left_child;
struct Node * right_child;
}Node;
Queue queue;
Stack stack;
void printZigZag(Node * head){
if(head == null){
return;
}
queue.push(head);
int row_number = 0;
int num_of_elements = 1;
int elements_covered_so_far = 0;
while(queue.size != 0){
Node * node = queue.pop();
if(node.type == PLACE_HOLDER){
continue;
}
elements_covered_so_far ++;
if(elements_covered_so_far == num_of_elements){
Node * place_holder = (Node*)malloc(sizeof(Node));
place_holder.type == PLACE_HOLDER;
queue.push(place_holder);
elements_covered_so_far = 0;
num_of_elements = num_of_elements * 2;
row_number++;
}
queue.push(node->left_child);
queue.push(node->right_child);
if(row_number % 2 ==1){
//print in reverse order
stack.push(node);
}
else{
printf("%d ",node->value);
}
if(stack.size() == num_of_elements){
while(!stack.is_empty()){
Node * node = stack.pop();
printf("%d ",node->value);
}
}
}
}
typedef struct Node{
int value;
char type;
struct Node * left_child;
struct Node * right_child;
}Node;
Queue queue;
Stack stack;
void printZigZag(Node * head){
if(head == null){
return;
}
queue.push(head);
int row_number = 0;
int num_of_elements = 1;
int elements_covered_so_far = 0;
while(queue.size != 0){
Node * node = queue.pop();
if(node.type == PLACE_HOLDER){
continue;
}
elements_covered_so_far ++;
if(elements_covered_so_far == num_of_elements){
Node * place_holder = (Node*)malloc(sizeof(Node));
place_holder.type == PLACE_HOLDER;
queue.push(place_holder);
elements_covered_so_far = 0;
num_of_elements = num_of_elements * 2;
row_number++;
}
queue.push(node->left_child);
queue.push(node->right_child);
if(row_number % 2 ==1){
//print in reverse order
stack.push(node);
}
else{
printf("%d ",node->value);
}
if(stack.size() == num_of_elements){
while(!stack.is_empty()){
Node * node = stack.pop();
printf("%d ",node->value);
}
}
}
}
Maintain two stacks, and push the children of the first stack onto the second. This naturally alternates the order of the rows. When the first stack is empty, swap the stacks. If still empty, we are done.
void PrintZigZag(node* pNode)
{
std::stack<node*> s1, s2, *pS1 = &s1, *pS2 = &s2;
bool bOdd = true;
s1.push(pNode);
while (pS1->size())
{
printf("%d ", pS1->top()->val);
node* pL = pS1->top()->pLeft;
node* pR = pS1->top()->pRight;
node* toPush[2] = {bOdd ? pR : pL, bOdd ? pL : pR};
pS1->pop();
for (node* pNext : toPush)
if (pNext)
pS2->push(pNext);
if (!pS1->size())
{
std::swap(pS1, pS2);
bOdd = !bOdd;
printf("\n");
}
}
}
output:
1
2 3
7 6 5 4
8 9
This problem is very similar to a Breath First Search graph algorithm where you go level by level and using a null value to mark the level.
I had this interview question once and I messed up. It worked but I used a Queue and Stack to reverse and a toggle flag to determine first Left then Right or first Right and then Left.
Instead of just dumping into a list and traverse using a toggle flag to determine the direction.
public static void PrintInZigZag(Node<T> root)
{
Queue<Node<T>> q = new Queue<Node<T>>();
bool left2right = false;
List<T> output = new List<T>();
q.Enquue(root);
q.Enqueue(null);
while(q.Count > 0)
{
Node val = q.Dequeue();
if(val == null)
{
PrintList(output, left2rigth);
left2rigth = ~left2rigth;
output.Clear();
q.Enqueue(null);
}
else
{
output.Add(val.Data);
if(val.Left != null)
{
q.Enqueue(val.Left);
}
if(val.Rigth != null)
{
q.Enqueue(val.Rigth);
}
}
}
}
private static void PrintList(List<T> output, bool forward)
{
int start = 0;
int end = output.Count -1;
int plus = 1;
if(!forward)
{
start = output.Count -1;
end = 0;
plus = -1;
}
for(int i = start; i != end; i += plus)
{
Console.Write(output[i].ToString() + " ");
}
Console.WriteLine(output[end]);
}
Something like the following could help. I did a level order recursive traversal and introduced a variable for direction.
public static void main(String[] args) {
ZigZagBT bt = new ZigZagBT();
Node root = bt.createBT();
int height = bt.getHeight(root, 0);
boolean ltr = false;
for (int i = 1; i <= height; i++) {
bt.traverse(root, i, ltr);
System.out.println();
ltr = !ltr;
}
}
private void traverse(Node node, int level, boolean ltr) {
if (node == null)
return;
if (level == 1) {
System.out.print(node.id);
} else if (level > 1) {
if (ltr) {
if (node.left != null) {
traverse(node.left, level - 1, ltr);
}
if (node.right != null) {
traverse(node.right, level - 1, ltr);
}
}else{
if (node.right != null) {
traverse(node.right, level - 1, ltr);
}
if (node.left != null) {
traverse(node.left, level - 1, ltr);
}
}
}
}
Almost identical to the most voted solution, but since I did the work I wanted to post it anyways.
Do breadth first search with 2 stacks and a variable for specifying the direction we are moving (left or right) so we can add the child nodes to the stacks in correct order.
/*
Tree:
20
/\
10 30
/\ /\
5 15 25 35
Output:
20
10 30
35 25 15 5
*/
function doZigZagOrderTest() {
var tree = new Tree();
[20, 10, 30, 5, 15, 25, 35].forEach(function (val) {
tree.add(val);
});
zigZagOrder(tree);
}
function zigZagOrder(tree) {
var currentStack = [tree.node];
var nextStack = [];
var printString = '';
var left = true;
while (currentStack.length > 0) {
var n = currentStack.pop();
if (n != null) {
printString += n.value + ' ';
if (left) {
nextStack.push(n.right);
nextStack.push(n.left);
} else {
nextStack.push(n.left);
nextStack.push(n.right);
}
}
if (currentStack.length === 0) {
currentStack = nextStack;
nextStack = [];
console.log(printString);
printString = '';
left = !left;
}
}
}
function Tree() {
this.node;
}
Tree.prototype.add = function (val) {
if (!this.node) {
this.node = new TreeNode(val);
} else {
this.node.add(val);
}
}
function TreeNode(val) {
this.value = val;
this.left;
this.right;
}
TreeNode.prototype.add = function (val) {
if (val === this.value) {
return;
} else if (val < this.value) {
if (!this.left) {
this.left = new TreeNode(val);
} else {
this.left.add(val);
}
} else {
if (!this.right) {
this.right = new TreeNode(val);
} else {
this.right.add(val);
}
}
}
Similar to what the folk here posted, but maybe slightly more structured and human-readable, but of course longer:
import java.util.Deque;
import java.util.LinkedList;
/**
* Created by Igor_Sokolov on 5/18/2015.
*/
public class CareerCup_5177676899811328 {
private static class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return String.valueOf(value);
}
}
private static Node prepareData() {
Node one = new Node(1);
Node two = new Node(2);
Node three = new Node(3);
Node four = new Node(4);
Node five = new Node(5);
Node six = new Node(6);
Node seven = new Node(7);
Node eight = new Node(8);
Node nine = new Node(9);
one.left = two;
one.right = three;
two.left = four;
two.right = five;
three.left = six;
three.right = seven;
four.left = eight;
four.right = nine;
return one;
}
public static void main(String[] args) {
Node root = prepareData();
printZigzag(root);
}
private static class Entry {
Node node;
int level;
public Entry(Node node) {
this.node = node;
this.level = 0;
}
public Entry(Node node, int level) {
this.node = node;
this.level = level;
}
public Entry subLeft() {
return (this.node.left != null) ? new Entry(this.node.left, this.level + 1): null;
}
public Entry subRight() {
return (this.node.right != null) ? new Entry(this.node.right, this.level + 1) : null;
}
}
private static void printZigzag(Node root) {
Deque<Entry>[] lists = new Deque[] {new LinkedList<>(), new LinkedList<>()};
add(lists, new Entry(root));
int level = 0;
while (!isEmpty(lists)) {
Entry e = enqueue(lists, level);
if (level != e.level) {
System.out.println();
}
System.out.print(e.node + " ");
Entry subLeft = e.subLeft();
if (subLeft != null) {
add(lists, subLeft);
}
Entry subRight = e.subRight();
if (subRight != null) {
add(lists, subRight);
}
level = e.level;
}
}
private static Entry enqueue(Deque<Entry>[] lists, int level) {
int idx = level % 2;
if (lists[idx].isEmpty()) {
return lists[(level + 1) % 2].removeFirst();
} else {
return lists[idx].removeFirst();
}
}
private static boolean isEmpty(Deque<Entry>[] lists) {
return lists[0].isEmpty() && lists[1].isEmpty();
}
private static void add(Deque<Entry>[] lists, Entry entry) {
if (entry.level % 2 == 0) {
lists[0].addFirst(entry);
} else {
lists[1].addLast(entry);
}
}
}
Using 2 stack approach
public String zigzag(Node root) {
StringBuilder ret = new StringBuilder();
Stack<Node> currentLevel = new Stack<>();
Stack<Node> nextLevel = new Stack<>();
boolean ltr = false;
currentLevel.push(root);
while (!currentLevel.isEmpty()) {
Node node = currentLevel.pop();
ret.append(node.value);
ret.append(", ");
if (ltr) {
if (node.left != null) {
nextLevel.add(node.left);
}
if (node.right != null) {
nextLevel.add(node.right);
}
}
else {
if (node.right != null) {
nextLevel.add(node.right);
}
if (node.left != null) {
nextLevel.add(node.left);
}
}
if (currentLevel.isEmpty()) {
ltr = !ltr;
Stack<Node> temp = currentLevel;
currentLevel = nextLevel;
nextLevel = temp;
}
}
return ret.toString().trim();
}
#include<bits/stdc++.h>
using namespace std;
typedef struct Node
{
int data;
Node *left;
Node *right;
};
stack<Node *> tmp;
stack<Node *> tmp1;
stack<Node *> hhh;
queue <Node *> Qu;
Node * Create(int data)
{
Node *xx=(Node *)malloc(sizeof(Node));
xx->data=data;
xx->left=NULL;
xx->right=NULL;
return xx;
}
void display(Node *root)
{
Node* a,b;
Qu.push(root);
while(!Qu.empty())
{
a=Qu.front();
Qu.pop();
cout<<" "<<a->data<<" "<<endl;
if(a->left)
Qu.push(a->left);
if(a->right)
Qu.push(a->right);
}
}
void zigzag(Node *root)
{
Node* a,b;
int i=1;
tmp.push(root);
while(!tmp.empty())
{
a=tmp.top();
cout<<a->data<<endl;
tmp.pop();
if(i%2==1)
{
if(a->right)
tmp1.push(a->right);
if(a->left)
tmp1.push(a->left);
}
if(i%2==0)
{
if(a->left)
tmp1.push(a->left);
if(a->right)
tmp1.push(a->right);
}
if(tmp.empty())
{
hhh=tmp;
tmp=tmp1;
tmp1=hhh;
i++;
}
}
}
int main()
{
Node *root=Create(1);
root->left=Create(2);
root->right=Create(3);
root->left->left=Create(4);
root->left->right=Create(5);
root->right->left=Create(6);
root->right->right=Create(7);
root->left->left->left=Create(8);
root->left->left->right=Create(9);
display(root);
zigzag(root);
return 0;
}
Here is C++ code using two stacks
void zigZagTraversal (treeNode *node)
{
using namespace std;
std::stack <treeNode *> LRQueue;
std::stack <treeNode *> RLQueue;
treeNode *currentNode;
bool leftToRight =true;
LRQueue.push (node);
while (!LRQueue.empty () || !RLQueue.empty ()) {
if (leftToRight) {
currentNode = LRQueue.top();
printf (" %d ", currentNode->x);
if (currentNode->r)
RLQueue.push (currentNode->r); //Insert right first
if (currentNode->l)
RLQueue.push (currentNode->l);
LRQueue.pop ();
if (LRQueue.empty ()) {
leftToRight=false;
printf ("\n");
}
}
else {
currentNode = RLQueue.top();
printf (" %d ", currentNode->x);
if (currentNode->l)
LRQueue.push (currentNode->l); //Insert left first
if (currentNode->r)
LRQueue.push (currentNode->r);
RLQueue.pop ();
if (RLQueue.empty ()) {
leftToRight=true;
printf ("\n");
}
}
}
printf ("\n");
}
Use BFS approach. Print all nodes of a given level in the same line, then print a new line
for i = 1 to height of tree {
call the recursive function breadthFirst below
System.out.println("*****");
}
private void breadthFirst(Node<V> node, int level) {
if (node == null) {
return;
}if (level == 0) {
System.out.print(node.value + " ");
} else if (level >= 1) {
breadthFirst(node.leftChild, level - 1);
breadthFirst(node.rightChild, level - 1);
}
}
- Vir Pratap Uttam May 10, 2015