Binary tree to Binary Search Tree (BST)

How can you convert Binary Tree to Bi开发者_StackOverflow中文版nary Search Tree with O(1) extra space ?

---

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.

---

Convert Binary Tree to a doubly linked list- can be done inplace in O(n) Then sort it using merge sort, nlogn Convert the list back to a tree - O(n)

Simple nlogn solution.