Should it be in-place? If not, you could create another tree and, while iterating through the binary tree, add nodes to the BST following the rules. Looks like O(n^2) in worst case (when you iterate through an ordered binary tree) and O(nlogn) in best case (when BST is balanced and adding takes logarithmic time).