Groupon Interview Question
InternsCountry: India
Interview Type: Written Test
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)
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>{
QueueNode<T> Head;
class QueueNode<T>{
T data;
QueueNode next;
public QueueNode(T data){
this.data=data;
}
}
public boolean enqueue(T data){
if(Head==null){
Head=new QueueNode<T>(data);
return true;
}
QueueNode temp=Head;
while(temp.next!=null){
temp=temp.next;
}
temp.next=new QueueNode<T>(data);
return true;
}
public T dequeue(){
QueueNode<T> temp=Head;
Head=Head.next;
return temp.data;
}
public boolean isEmpty(){
return Head==null;
}
}
class TestCase{
static Node firstLeaf=null;
static Node prevLeaf=null;
public static void main(String[] args) throws IOException{
BufferedReader buf=new BufferedReader(new InputStreamReader(System.in));
String str=buf.readLine();
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
}
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
if(head==NULL) //initialize head with the first leaf node
head = nd;
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);
}
This problem can be solved Traverse root to leaf node and leaf traverse from left to right ...will post solution soon
- Satveer August 13, 2013