Binary tree to Binary Search Tree (BST)

Converting an unordered binary tree into an ordered binary search tree is trivial, but a bit more difficult to do fast.\n\nHere's a naive implementation that should satisfy your criteria, I will not describe the actual steps to take, just the overall algorithm.\n\n\nGrab a random leaf node from your existing tree\nUnlink the leaf node from your existing tree\nMake the node the root of your new binary search tree\nGrab another random leaf node from your existing tree\nUnlink that node from your existing tree\nFind the right spot for, and link the node, into your new binary search tree\nRepeat step 4-6 until the original tree is empty\n\n\nYou should require only a few variables, like the parent of the leaf node you're unlinking (unless the nodes has parent-links), the root node of the new tree, and a couple of temporary variables, all within your O(1) space criteria.\n\nThis will not produce an optimal binary search tree. For that you need to either sort the nodes before adding them, and adding them in the right order, or use a balancing binary search tree, like a red-black tree or a splay tree.",