Amazon Interview Question
Software Engineer / DevelopersCountry: India
public List<Node> getOrderedNodes(Node rootNode) {
List<Node> result = new LinkedList<Node>();
Stack<Node> currentLevel = new Stack<Node>();
Stack<Node> nextLevel = new Stack<Node>();
currentLevel.push(rootNode);
boolean isLeftToRight = true;
while( !currentLevel.isEmpty() ){
Node currentNode = currentLevel.pop();
if( currentNode != null ){
result.add(currentNode);
if(isLeftToRight){
nextLevel.push(currentNode.getLeft());
nextLevel.push(currentNode.getRight());
}else{
nextLevel.push(currentNode.getRight());
nextLevel.push(currentNode.getLeft());
}
}
if(currentLevel.isEmpty()){
isLeftToRight = !isLeftToRight;
Stack<Node> temp = currentLevel;
currentLevel = nextLevel;
nextLevel = temp;
}
}
return result;
}
You can find this question on Leetcode online judgement,
The question is "Binary Tree Zigzag Level Order Traversal"
just like a normal level order traversal..maintain a queue. Use some extra variable to track, how elements are to be printed viz. for even level they be printed in the same sequence they are present in queue and for odd level they are printed in reverse order.
void func(struct node *ptr)
{
if(ptr==NULL)
return;
int n;
n=numNodes(ptr);
struct node *arr[n]={NULL}; //n is the number of nodes in tree..initialize array to NULL
int cl,nl,level,count,index,p,q,i;
arr[0]=ptr;
nl=count=index=0;
p=q=0;
cl=1;
while(arr[index]!=NULL)
{
if(level==0)
printf("%d",arr[0]->num);
cl--;
if(arr[index]->left!=NULL)
{
arr[++count]=ptr->left;
nl++;
}
if(arr[index]->left!=NULL)
{
arr[++count]=ptr->right;
nl++;
}
if(cl==0)
{
p=q;
q=index;
cl=nl;
nl=0;
if(!(level%2)) //even level
{
i=p+1;
while(i<=q)
{
printf("%d",arr[i]->num);
i++;
}
}
else //odd level
{
i=q;
while(i>p)
{
printf("%d",arr[i]->num);
i--;
}
}
level++;
}
index++;
}
}
- Vir Pratap Uttam May 04, 2015