CareerCup

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

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.

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 for thisat Ideone: ideone.com/dB4Usn

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

}

please give code in C language

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);
}

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.