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!

Answer 2

"Balanced as possible" = complete (or full) binary tree¹. You cannot get more balanced that it.

The solution is simple - build an "empty" complete binary tree, and iterate the new tree and the input tree (simultaneously) in inorder-traversal to fill the complete tree.

When you are done, you have the most balanced tree you can get, and time complexity of this approach is O(n).

---

EDIT:
This should be done following these steps:

1. Build a dummy complete tree with n nodes. All the values to each node will be initialized to some garbage value.
2. Create two iterators: (1) originalIter for the original tree, (2) newIter for the new (initialized with garbage) tree. Both iterators will return elements in in-order traversal.

3. Do the following to fill the tree with the values from the original:

    while (originalIter.hasNext()):
         newIter.next().value = originalIter.next().value
   

---

(1) (From Wikipedia): A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible

Answer 3

The DSW algorithm can solve this is O(n) time. The algorithm goes as follows:

1] Using right-rotation operations, turn the tree into a linked list
   (a.k.a. backbone or vine)
2] Rotate every second node of the backbone about its parent to turn
   the backbone into a perfectly balanced BST. 

Reference

Answer 4

This will convert your normal BST into a balanced BST with minimum possible height in O(n). First, save all your nodes sorted into a vector. Then, the root is the mid element and recursively build a tree from 0 to mid-1 as its left and build a tree from mid+1 to vector.size()-1 as its right child. After all these steps root keeps the balanced BST with the min-height.

    import java.util.Vector;

        public class ConvertBSTIntoBalanced {

            public static void main(String[] args) {
                TreeNode node1 = new TreeNode(1);
                TreeNode node2 = new TreeNode(2);
                TreeNode node3 = new TreeNode(3);
                TreeNode node4 = new TreeNode(4);
                node1.right = node2;
                node2.right = node3;
                node3.right = node4;
                ConvertBSTIntoBalanced convertBSTIntoBalanced = new ConvertBSTIntoBalanced();
                TreeNode balancedBSTRoot = convertBSTIntoBalanced.balanceBST(node1);
            }

            private void saveNodes(TreeNode node, Vector<TreeNode> nodes) {
                if (node == null)
                    return;
                saveNodes(node.left, nodes);
                nodes.add(node);
                saveNodes(node.right, nodes);
            }

            private TreeNode buildTree(Vector<TreeNode> nodes, int start, int end) {
                if (start > end)
                    return null;
                int mid = (start + end) / 2;
                TreeNode midNode = nodes.get(mid);
                midNode.left = buildTree(nodes, start, mid - 1);
                midNode.right = buildTree(nodes, mid + 1, end);
                return midNode;
            }

            public TreeNode balanceBST(TreeNode root) {
                Vector<TreeNode> nodes = new Vector<>();
                saveNodes(root, nodes);
                return buildTree(nodes, 0, nodes.size() - 1);
            }

        public class TreeNode {

        public Integer val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(Integer x) {
            val = x;
        }

    }

        }

I hope it helps.