## Groupon Interview Question for Interns

Country: India
Interview Type: Written Test

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

This problem can be solved Traverse root to leaf node and leaf traverse from left to right ...will post solution soon

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

Traverse the BST in in-order and when any leaf node is encountered, point it's left pointer to it's parent . for right pointer, store the leafnode as prevLeafNode and when a new leaf node is found point prevLeafNode to new Leafnode.
Working on the code , will post it soon.

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

If I don't understand wrong, same as InOrderTreeWalker

walker(i)
{
if(i != null){
walker(i.left)
if(i.hasChild)
change ptr
else
change ptr for leaf
walker(i.right)
}
}

Go each node exactly twice, o(n)

Comment hidden because of low score. Click to expand.
0

Hi,
Where are you changing right pointer of non-leaf node to NULL?

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

Working code for thisat Ideone: ideone.com/dB4Usn

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

Working code:

``````import java.io.*;
class Node<T>{
T data;
Node<T> left;
Node<T> right;
public Node(T t){
this.data=t;
}
}
class Queue<T>{
class QueueNode<T>{
T data;
QueueNode next;
public  QueueNode(T data){
this.data=data;
}
}
public boolean enqueue(T data){
return true;
}
while(temp.next!=null){
temp=temp.next;
}
temp.next=new QueueNode<T>(data);
return true;
}
public T dequeue(){
return temp.data;
}
public boolean isEmpty(){
}

}
class TestCase{
static Node firstLeaf=null;
static Node prevLeaf=null;
public static void main(String[] args) throws IOException{
if(str==null || str.length()<=0){
System.out.println("Invalid Input");
return;
}
String[] inpString=str.split(",");
int[] inp=new int[inpString.length];
for(int i=0;i<inpString.length;i++){
inp[i]=Integer.parseInt(inpString[i]);
}
Node<Integer> rootBST= createBSTFromArray(inp,0,inp.length-1);
printBST(rootBST);
convertBST(rootBST);

Node rnode=firstLeaf;
while(rnode.right!=null){
Node temp=rnode;
while(temp.left!=null){
System.out.print(" "+temp.data+"-->"+temp.left.data);
temp=temp.left;
}
System.out.println(" "+rnode.data+"-->"+rnode.right.data);
rnode=rnode.right;
}
}
public static void printBST(Node node){
Queue<Node> queue=new Queue<Node>();
queue.enqueue(node);
queue.enqueue(null);
while(!queue.isEmpty()){
Node temp=queue.dequeue();
if(queue.isEmpty())break;
if(temp==null){
queue.enqueue(null);
System.out.println(" ");
}else{
System.out.print(" "+temp.data);
if(temp.left!=null)queue.enqueue(temp.left);
if(temp.right!=null)queue.enqueue(temp.right);
}

}
}
public static Node convertBST(Node root){
System.out.println("calling for root"+root.data);
if(root.left==null && root.right==null){
System.out.println("returned leaf"+root.data);
if(firstLeaf==null)firstLeaf=root;
System.out.println("firstleaf is"+firstLeaf.data);
if(prevLeaf==null){
prevLeaf=root;
}else{
prevLeaf.right=root;
System.out.println("prev leaf and new leaf"+ prevLeaf.data+" "+root.data);
prevLeaf=root;
}
return root;
}else{
if(root.left!=null) {
System.out.println("left is"+root.left.data);
convertBST(root.left);
root.left.left=root;
root.left.right=null;
root.left=null;

}
if(root.right!=null) {
System.out.println("right is"+root.right.data);
convertBST(root.right);
root.right.left=root;
root.right.right=null;
root.right=null;

}
}

return root;

}

public static Node<Integer> createBSTFromArray(int[] inp,int from,int to){
//System.out.println("from and to "+from+" "+to);
if(inp.length==0 || from>to)return null;
if(from==to && to-from==0)return new Node<Integer>(inp[to]);
int root=from+(to-from)/2;
Node<Integer> rootNode=new Node<Integer>(inp[root]);
rootNode.left=createBSTFromArray(inp,from,root-1);
rootNode.right=createBSTFromArray(inp,root+1,to);
System.out.println("for node"+ inp[root]);
if(rootNode.left!=null){
System.out.println(" left node is"+rootNode.left.data);}
else{
System.out.print(" left node is null");
}
if(rootNode.right!=null){
System.out.print(" right node is"+rootNode.right.data);}
else{
System.out.print(" right node is null");
}

return rootNode;
}
//fuction for converting BST to new format``````

}

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

please give code in C language

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

I think this should work.

``````struct node* changebst( struct node* nd, struct node* par, struct node* prev, struct node* head)
{
if(nd->left==NULL && nd->right==NULL)		//leaft node
{
if(prev!=NULL)
prev->right = nd;					//the previous leaf node traversed
nd->left = par;
return(nd);
}
struct node* x;
if(nd->left!=NULL)
x = changebst(nd->left,nd,prev);				//x stores the last leaft node traversed
else
x = prev;
nd->left = p;
if(nd->right!=NULL)
x = changebst(nd->right,nd,x);
nd->right = NULL;
return(x);
}``````

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

Since we need to change left and right pointers, I think post order walk will work as well. Just keep tracking the previous leaf as OTR mentioned.

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.

### 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.