Converts a binary tree to binary search tree

BTtoBST.java

class BTtoBST
{   
    static ArrayList<Integer> inOrder(Node root, ArrayList<Integer> orig){
        if(root==null) return orig;
        
        inOrder(root.left, orig);
        orig.add(root.data);
        inOrder(root.right, orig);
        
        return orig;
    }
    
    Node createBST(Node current,Node bstcurrent,HashMap<Integer,Integer> hm, ArrayList<Integer> sorig){
        
        if(current==null) return null;
        
        bstcurrent = new Node(sorig.get(hm.get(current.data)));
        
        bstcurrent.left = createBST(current.left,bstcurrent.left,hm,sorig);
        bstcurrent.right= createBST(current.right,bstcurrent.right,hm,sorig);
        
        return bstcurrent;        
    }
    
    
    Node BTtoBST(Node root)
    {
        ArrayList<Integer> orig = new ArrayList<Integer>(),sorig= new ArrayList<Integer>();
        orig = inOrder(root,orig);
        HashMap<Integer,Integer> hm = new HashMap<Integer, Integer>();
        
        for(int i=0; i<orig.size(); i++){
            sorig.add(orig.get(i));
            hm.put(orig.get(i),i);
        }
        
        Collections.sort(sorig);
        
        Node bstroot =null;        
        
        bstroot = createBST(root,bstroot,hm,sorig);    
        
        
        return bstroot;
    }
}