Binary Tree to BST

Binary Tree to BST

  August 08, 2017    

---

Idea is to find inorder of tree and sort the  values.

Again perform inorder but now change the values to sorted values


Code:

class hackerranksolutionc
{
    int index=0;
    void inorder(List<Integer> lst,Node root)
    {
        if(root==null)
        return ;
        if(root.left!=null)
        inorder(lst,root.left);
        
        lst.add(root.data);
        if(root.right!=null)
        inorder(lst,root.right);
    }
      void change(List<Integer> lst,Node root)
    {
        if(root==null)
        return ;
        if(root.left!=null)
        change(lst,root.left);
        
        root.data=lst.get(index++);
        if(root.right!=null)
        change(lst,root.right);
    }
    Node binaryTreeToBST(Node root)
    {
 if(root==null)
 return null;
 
 List<Integer> lst=new ArrayList<Integer>();
 inorder(lst,root);
 Collections.sort(lst);
 change(lst,root);
 return root;
    }
}