Rebalancing an arbitrary BST?

Question

Reference: I was asked this question @MS SDE interview, 3rd round. And it's not a homework problem. I also gave it a thought and mentioning my approach below.

Question: Modify a BST so that it becomes as balanced as possible. Needless to mention, you should do it as efficient as possible.

Hint: Interviewer said that this is a logical question, if you think differently you will get the answer. No difficult coding involved.
--> Having said that, I do not think he was expecting me to point to AVL/RB Trees.

My Solution: I proposed that, I would do inorder traversal of tree, take middle element as root of new tree(lets call it new root). Then go to the left part of middle element, take its middle element as root of left subtree of tree rooted new root. Similarly do for right part. Doing this recursively will give the optimal balanced BST.

Why I am posting it here: But he was not satisfied with the answer :( So, is there really a way of doing this w/o going for weights/RB coloring strategy, or was he just fooling around with me? Please put in your expert thoughts.

Duplicate? No! I know there is this question but the solution proposed by requester is too complicated, and other one talks about AVL trees.

Answer 1

You might want to look into the Day-Stout-Warren algorithm, which is an O(n)-time, O(1)-space algorithm for reshaping an arbitrary binary search tree into a complete binary tree. Intuitively, the algorithm works as follows:

1. Using tree rotations, convert the tree into a degenerate linked list.
2. By applying selective rotations to the linked list, convert the list back into a completely balanced tree.

The beauty of this algorithm is that it runs in linear time and requires only constant memory overhead; in fact, it just reshapes the underlying tree, rather than creating a new tree and copying over the old data. It is also relatively simple to code up.

Hope this helps!