CareerCup

Algo:
Use 1 stack and 1 queue.. Add node to queue. Get the top node from queue. Push all children in queue. When all children have been pushed, add the node to stack and repeat. at end print the stack....

psuedocode:

initQueue(Q)
initStack(S)
enqueue(Q, root)
while (!isEmpty(Q) {
      node = dequeue(Q);
      for (i = 0; i < node->childrens; i++)
            enqueue(Q, node[i]);

     push(S,node);
}

while(!isEmpty(S))
    print(pop(s));

insert the nodes in the queue like normal BFS .but use a dequeue and insert till all elements are done. after that remove from the rear of the queue(the side where last element was inserted).

<Extended Problem>
It would have been interesting if the question also asked to print the level number along with its elements. To be more clear, since this is ReverseBFS, an output like:
Level n : Node 100,99,88,
Level n-1: ......
Level n-2: ...................

Just wondering with the same datastructure of queue that we are currently using, can we also infer level?

Simply pushing the values in Queue (right to left), and then pushing them to stack (so that values can later be printed left to right) won't fetch us level number. Am I right here?
Do we need a dummy separator element for marking the end of a level?

it is simple, but your answer is wrong Singleton. You know nothing about the internal structure of a Node. You just have the interface. nothing in the problem statement says that you know there is a node.left or a node.right. you just have access to children. The simplest and most obvious method is to use recursion.

#In normal BFS, we normally start with putting root in a queue. Then while queue is not empty, we take the front node, enqueue it's 2 (or n) children, and print the node's data.
#The variation in this problem would be - instead of printing the node's data, push the node onto a stack. And when the queue becomes empty, print all stack nodes.

Makes sense?

package interview.tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class Q13870718
{
    static class Node
    {
        private String data;
        private List<Node> children;

        public Node(final String data)
        {
            this.data = data;
            this.children = new ArrayList<Node>();
        }
        
        public Node(final String data, final Node... children)
        {
            this.data = data;
            this.children = new ArrayList<Node>(Arrays.asList(children));
        }

        public String getNodeData()
        {
            return this.data;
        }

        public List<Node> getChildren()
        {
            return Collections.unmodifiableList(this.children);
        }        
    }
    
    public static void displayBFSReverse(final Node head)
    {
        Stack<Node> s = new Stack<Node>();
        Queue<Node> q = new LinkedList<Node>();
        q.add(head);
        Node cur;
        while((cur = q.poll()) != null)
        {
            s.push(cur);
            for (Node child : cur.getChildren())
            {
                q.offer(child);
            }
        }
        
        while(!s.empty())
        {
            System.out.print(s.pop().getNodeData() + " ");
        }
    }

    public static void main(String[] args)
    {
        Node tree = new Node(
            "34", 
                new Node("3", 
                    new Node("89"), 
                    new Node("7")),
                new Node("56"),
                new Node("12",
                    new Node("22",
                        new Node("78"))));
        
        System.out.print("BFSReverse: "); displayBFSReverse(tree); System.out.println(); 
    }
}

Why do people put their homework question as google interview questions???

we can implement it with bredth first search algo using stack

public void BFSTranverse(Node startNode) {
while (startNode != null) {
if (startNode.childs != null && startNode.childs.size() > 0) {
for (int i = 0; i < startNode.childs.size(); i++) {
queue.add(startNode.childs.get(i));
}
}
count ++;
startNode = queue.size() > count ? queue.get(count) : null;
}
Collections.reverse(queue);
for (Node node: queue) {
System.out.print(node.data + " ");
}
}

store the nodes you walk in normal BFS in a list. Reverse the list. Print.

Use BFS, but instead of printing the node values, push it to the stack.
Once BFS gets completed, print the stack.

public void displayTree_BreadthFirst(Node root) {
        Queue<Node> queue = new LinkedList<Node>();
        Stack<Node> stack = new Stack<Node>();
        queue.add(root);
        stack.push(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.printf("%3d", node.element);
            if (node.left != null) {
                queue.add(node.left);
                stack.push(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
                stack.push(node.right);
            }
        }
        System.out.println();
        while (!stack.isEmpty()) {
            System.out.printf("%3d", stack.pop().element);
        }
    }

Output:
Regular BFS = 1 2 3 4 5 6
Reverse BFS = 6 5 4 3 2 1

Space = Queue + Stack.

Question sounds fairly simple, was it asked without additional storage or only using a Queue and no stack?

This is definitely homework question!!
This guy has posted the same question under Google and Amazon..
Even if u were asked the same question in both the interviews(probability is very less) why is there any need to put the same question twice?

void ReverseBFS(Node* root) 
{
   if (!root)
       return;

   List<Node*> children = root->getChildren();
   
   while(!end of children) {
        ReverseBFS(child);
   }
   
   cout << root->PrintData();
   return;
}