Binary tree to BST

Question

How wil you convert Binary Tree to Binary Search Tree with O(1) extra space ?

Answer 1

Converting an unordered binary tree into an ordered binary search tree is trivial, but a bit more difficult to do fast.

Here's a naive implementation that should satisfy your criteria, I will not describe the actual steps to take, just the overall algorithm.

1. Grab a random leaf node from your existing tree
2. Unlink the leaf node from your existing tree
3. Make the node the root of your new binary search tree
4. Grab another random leaf node from your existing tree
5. Unlink that node from your existing tree
6. Find the right spot for, and link the node, into your new binary search tree
7. Repeat step 4-6 until the original tree is empty

You 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.

This 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.