CareerCup

q1.enqueue(head)
while(!q1.empty() && !q2.empty())
{

while(!q1.empty)
{
temp = q1.dequeue();
q3.enqueue(temp);
q2.enqueue(temp.left); // check for null
q2.enqueue(temp.right);// check for null
}
q3.enqueue("#");


while(!q2.empty)
{
temp = q2.dequeue();
q3.enqueue(temp);
q1.enqueue(temp.left);// check for null
q1.enqueue(temp.right);// check for null
}
q3.enqueue("#");
}

while(!q3.empty())
{
temp = q3.dequeue()
if(temp == "#")
sysoutprintln();
else
sysoutprint(temp);
}

My solution is :

#include<stdio.h>
#include<stdlib.h>
struct node
{
  int data;
  struct node *right;
  struct node *left;
}*root;
struct node *createnode(int k)
{
  struct node *nwnode=malloc(sizeof(struct node));
  nwnode->data=k;
  nwnode->left=NULL;
  nwnode->right=NULL;
  return nwnode;
}
void PrintLevelNodeBottomUp(struct node *t)
{
	if(t==NULL)
	   return;
	struct node *List[20];
	int m;
	for(m=0;m<20;m++)
	   List[m]=NULL;
        int i=0;
        int j=0;
	List[i++]=t;
	struct node *pP=List[0];
	List[i++]=createnode(-1);
	while(pP!=NULL && List[j+1]!=NULL)
	{
		if(pP->right!=NULL && pP->data!=-1)
		   List[i++]=pP->right;
		if(pP->left!=NULL && pP->data!=-1)
		   List[i++]=pP->left;
		if(pP->data==-1)
		   List[i++]=createnode(-1);
		pP=List[++j];
	}
	for(m=i-1;m>=0;m--)
	{
	  if(List[m]->data==-1)
	     printf("\n");
          else
	    printf("%d ",List[m]->data);
	}
}
int main(int args,char *argv[])
{
  root=createnode(11);
  root->left=createnode(4);
  root->right=createnode(15);  
  root->left->left=createnode(3);
  root->left->right=createnode(8);
  root->left->left->left=createnode(7);
  root->left->left->left->left=createnode(1);
  root->right->left=createnode(10);
  root->right->right=createnode(16);
  root->right->right->right=createnode(14);
  root->right->left->left=createnode(5);
  root->right->right->right->right=createnode(2);
  PrintLevelNodeBottomUp(root);
}

It will take 0(n) time and O(nlogn) space , I am sure there is much better solution possible.

It is simple to code using recursion, but not efficient considering the stack space.

public static void ReverseLevelOrder(Node root)
{
    Queue queue=new Queue();
    queue.enqueue(root);
    Recursive(queue);
    System.out.println(root.value);
}
public static void Recursive(Queue queue)
{
    if(queue.isEmpty())
        return;
    Queue newqueue=new Queue();
    while(!queue.isEmpty())
    {
        TreeNode n=queue.dequeue();
        if(n.left!=null)
            newqueue.enqueue(n.left);
        if(n.right!=null)
            newqueue.enqueue(n.right);
    }
    Recursive(newqueue.clone());
    while(!newqueue.isEmpty())
        System.out.print(" "+newqueue.dequeue().value);
    System.out.println();
}

Call the first function which will call the recursive function.

I think this is better approach, basically u maintain two pointers currrent and nextlevel

static void printbottomtop(Node head)
        {
            int current=1, nextleval = 0;
            int index = 1;
            List<Object> nodes = new List<Object>();
            nodes.Add("#");
            nodes.Add(head);
            nodes.Add("#");
            while (true)
            {
                while (current > 0)
                {
                    Node n = (Node)nodes[index];
                    if (n.left != null)
                    {
                        nodes.Add(n.left);
                        nextleval++;
                    }
                    if (n.right != null)
                    {
                        nodes.Add(n.right);
                        nextleval++;
                    }
                    current--;
                    index--;
                }
                if (current == 0 && nextleval == 0)
                {
                    break;
                }
                else
                {
                    nodes.Add("#");
                    index = nodes.Count - 1-1;
                    current = nextleval;
                    nextleval = 0;
                }
            }
            //Now print nodes from bottom-up approach
            index = nodes.Count - 1;
            while (index>0)
            {
                if (nodes[index].ToString().Equals("#"))
                {
                    Console.WriteLine();
                }
                else
                {
                    Console.Write(((Node)nodes[index]).data.ToString()+" ");
                }
                index--;

            }

            
        }

public int findlevel() {
BinaryTreeNode prv = root;
if (root == null)
return 0;
int level = 0;
queue.add(root);
queue.add(null);
LinkedList<BinaryTreeNode> levelnodes=new LinkedList<BinaryTreeNode>();
while (!queue.isEmpty()) {
BinaryTreeNode temp = queue.remove();
if (temp != null)
{
prv = temp;
levelnodes.add(prv);
}
if (temp == null) {
level++;
LinkedList<BinaryTreeNode> l=new LinkedList<BinaryTreeNode>(levelnodes);
levelnode.put(level,l);
levelnodes.clear();
if (!queue.isEmpty())
queue.add(null);

} else {
if (temp.getLeft() != null) {
queue.add(temp.getLeft());
}
if (temp.getRight() != null)
queue.add(temp.getRight());

}

}
System.out.print("Level" + level);
queue.clear();
return level;
}

Since we need to preserve the nodes while traversing, instead of using Queue for maintaining the nodes, lets use vector and take care of indexes when we change levels. I am using an "empty" node to separate out two levels.

void PrintLevelOrderList(Node * root)
{
   //if (root) do some validation

   static Node * empty =  new Node (empty); // Have some empty node, store it somewhere or create everytime

   std::vector<Node *> levelOrderList;
   levelOrderList.append(root);
   levelOrderList.append(empty);
   int index = 0; 
  
   while (true) 
   {
       Node * curr = levelOrderList[index];
       if (curr != empty)
       {
          if (curr->lc)
            levelOrderList.append(curr->lc);
          if (curr->rc)
           levelOrderList.append(curr->rc);
       }
      else
      {
          if (index == levelOrderList.size() - 1) // This is the last element
         { 
            // Hence it should terminate
             break;
          }
          else
          {
             // We have more elements, but we are done with with one level
             levelOrderList.append(empty);
          }
      } // else block
      index++;
    }// while (true) 
   
    // We should now be having a the list in the level order format. 
   // Use reverse iterators to print the nide,
   std::vector<Node *> :: reverse_iterator iter = levelOrderList.rbegin();
   while (iter != levelOrderList.rend())
   {
      if (*iter != empty)
         cout<<*iter;
      else
         cout << std::endl;
   } 
   
 }

Good ques ...
Here is my approach ...
Have a queue , stack and a vector (to keep track how many nodes in each level.
As usual push the root in the queue.
Pop the root and push its right child followed by left in the queue.
Store the root in the stack.
use the Vector to keep track of how many nodes have been explored at each level.

This is my code

void print_reverse_level_order(struct node* tree)
{
    std::queue<struct node*> Queue;
    std::stack<int> Stack;
    std::vector<int> V;

    if(tree==NULL)
        return;
    Queue.push(tree);
    V.push_back(1);
    while(!Queue.empty())
    {
        struct node* v=Queue.front();
        struct node* x;
        if(v->right!=NULL)
            x=v->right;
        else if(v->left!=NULL)
            x=v->left;
        else
        {
            x=NULL;
            Queue.pop();
            Stack.push(v->val);
            continue;
        }

        int k=0;
        while(x!=NULL && v!=x)
        {
            Stack.push(v->val);
            k++;
            if(v->right!=NULL)
                Queue.push(v->right);
            if(v->left!=NULL)
                Queue.push(v->left);
            Queue.pop();
            v=Queue.front();
        }
        V.push_back(k);
    }
    for(int i=V.size()-1;i>=0;i--)
    {
          std::cout<<"\nLevel:"<<i;
          for(int j=0;j<V[i];j++)
          {
              int d=Stack.top();
              std::cout<<" "<<d;
              Stack.pop();
          }
          std::cout<<"\n";
    }
    return;
}

Simpler solution using queue and two stacks.
1. Doing a level order traversal using queue, also push the node into stack1 along with the level they are on.
2. Once we have reached the end, ie. queue is empty, start popping nodes from stack1 and push them into stack2.
3. When you see a change in level on the stack1, print out all elements in stack2 and then push the new node into stack2.
4. Once stack1 is empty, check if there are elements in stack2 and print them.

Any issues with this method?