Groupon Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
6
of 6 vote

Use a queue for level order traversal and a stack to print the data in reverse order.

void reverseLevelOrderPrint (Node* root)
  {
    Stack S;
    Queue Q;
    Q.enqueue(root);
    while (!Q.empty())
    {
       Node* n = Q.dequeue();
       S.push(n);
       if (n->right)
         Q.enqueue(n->right)
       if (n->left)
         Q.enqueue(n->left)
    }
    while(!S.empty())
    {
      Node* n = S.pop();
      cout << n->data << "  ";
    }
  }

- Anonymous December 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can't we use the stack directly?

- dinnu.k December 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

No need to use two data structures....can be done with an array or arraylist only

- Anshul December 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is how I did it too. I don't see anything wrong with this method. Especially since an arraylist with a very large tree would run out of memory since on reallocation it doubles the size..

- Anonymous December 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

good approach.

- aaman.singh85 April 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void LevelOrderHelper(Node root)
{
if (root == null)
return;

int height = Height(root);

for (int i = height; i >= 1; i--)
{
LevelOrderRecursive(root, i);
Console.WriteLine();
}
}

void LevelOrderRecursive(Node root, int level)
{
if (root == null)
return;

if (level == 1)
{
Console.Write(root.data);
}
else
{
LevelOrderRecursive(root.left, level - 1);
LevelOrderRecursive(root.right, level - 1);
}
}

int Height(Node root)
{
if (root == null)
{
return 0;
}

int leftHeight = Height(root.left);
int rightHeight = Height(root.right);

if (leftHeight > rightHeight)
return leftHeight + 1;
else
return rightHeight + 1;
}

static void Main()
{
TreeProblems t = new TreeProblems();

Node root = new Node(1);

Node level1Child1 = new Node(2);
Node level1Child2 = new Node(3);

Node level2Child1 = new Node(4);
Node level2Child2 = new Node(5);
Node level2Child3 = new Node(6);
Node level2Child4 = new Node(7);

root.left = level1Child1;
root.right = level1Child2;

level1Child1.left = level2Child1;
level1Child1.right = level2Child2;

level1Child2.left = level2Child3;
level1Child2.right = level2Child4;

t.LevelOrderHelper(root);

Console.ReadLine();
}

- siva December 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 6 vote

1.Use array if you know size of tree else use arraylist
2.Keep adding right and left child until you reach at the end of tree.
3.Print elements of arraylist in revese order.
Time:O(n)
Space:O(n)

Here is a sample implementation in java:

public static void printReverseLevelOrder(TreeNode root) {
		if (root == null)
			return;
		ArrayList<TreeNode> deque = new ArrayList<TreeNode>();
		deque.add(root);
		for (int i = 0; i < deque.size(); i++) {
			TreeNode node = deque.get(i);
			if (node.right != null) {
				deque.add(node.right);
			}
			if (node.left != null) {
				deque.add(node.left);
			}
		}
		for (int i = deque.size() - 1; i >= 0; i--) {
			System.out.print(deque.get(i).data);
		}
	}

- Anshul December 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this approach is fine, but so is the approach using a stack based on a linked-list tree implementation. If the tree is far from complete, the array-based solution would waste a lot of space and a linked-list solution would be a better choice, so which solution approach to choose would depend on the trees in question.

- Anonymous December 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Analyze it...it won't take much extra space because I am using arraylist....which expands itself dynamically...

- Anshul December 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The output of your code will give 7 6 5 4 3 2 1 rather than 4 5 6 7 2 3 1.

- viswa February 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@viswa - it wont print like the way u mentioned it. The code adds the right nodes before the left ones. So the code works fine

- Karthik February 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Space taken in this approach would be O(n). You can argue that *might be* at (n-1)th node, this arraylist may expand and might take O(2n). If it is a concern then you can take a queue implemented with doubly-linled list. here space would be O(n) and you can traverse it reversely.
It is a better option than to use a queue+stack, as it will always consume O(2n) space.

- rvm December 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

"pseudocode"

print_at_depth(int n,tree * t)
{
    if(t == Null) return;

    if(n==0)
    { 
      print(t->value);
      return;
    }

    print_at_depth(n-1,t->left);
    print_at_depth(n-1,t->right);
}

int max_tree_depth(tree * t)
{
    if(t == Null) return 0;
    return 1 + max(max_tree_depth(t->left),max_tree_depth(t->right)); 
}

//solution

solver(tree * t)
{
    int max_d = max_tree_depth();
    for(int i=max_d;i>=0;i--)
    {
         print_at_depth(i,t);
    }
}

- Anonymous December 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void levelwise_reverse(btnode* root)
{
   if(root) {
       queue<btnode*> q;
	   stack(<btnode*> stk;
	   
	   q.enqueue(root);
	   while(!q.empty())
	   {
	      btnode* curr = q.dequeue();
		  stk.push(curr);
		  
		// Note we are enqueuing right node before left (diff from usual bfs level wise traversal)
		 if(curr->right)
		     q.enqueue(curr->right);		  
		  
		  if(curr->left)
		     q.enqueue(curr->left);
			
		}
		
		while(!stk.empty())
		{
		   cout<<stk.top();
		   stk.pop();
		   
		}
	}
}

- foobar December 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

just as doing BFS, en-queue the root, then its right child and then the left child, repeat the process for each node in the queue from the front until NULL. print the queue from the rear to front.

- Anonymous December 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo.

This can be acheived y performing an BFS in a right to left manner and loading the node data into a stack.
The stack can be printed which would print the values from left to right.

refre the geeksforgee**s BFS logic using recusruion.

- Sandeep Balle Chandrasekaran February 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a Doubly-Linked List, add root first, then traverse through the list, for each node, add its children into the list. In the end, traverse backwards to print all.

- Zoro June 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using Recursion :

public void printReverseLevelOrder() {
		if (this.root == null) {
			return;
		} else {
			Queue<Node<K, V>> nodeQueue1 = new LinkedList<Node<K, V>>();
			nodeQueue1.add(root);
			System.out.println(printReverseLevelOrderHelper(nodeQueue1));
		}
	}
	
	public String printReverseLevelOrderHelper(Queue<Node<K, V>> nodeQueue1){
		StringBuilder output = new StringBuilder();
		Queue<Node<K, V>> nodeQueue2 = new LinkedList<Node<K, V>>();
		while (!nodeQueue1.isEmpty()) {

			Node<K, V> curNode = nodeQueue1.remove();
			output.append(curNode.value + " ");
			if (curNode.leftchild != null) {
				nodeQueue2.add(curNode.leftchild);
			}
			if (curNode.rightchild != null) {
				nodeQueue2.add(curNode.rightchild);
			}
		}
		if(!nodeQueue2.isEmpty()){
			System.out.println(printReverseLevelOrderHelper(nodeQueue2));
		}
		return output.toString();
	}

- Punit July 19, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More