Question

a. How can I show that any node of a binary search tree of n nodes can be made the root in at most n − 1 rotations?

b. using a, how can I show that any binary search tree can be balanced with at most O(n log n) rotations (“balanced” here means that the lengths of any two paths from root to leaf differ by at most 1)?

Answer 1

a. We know that a binary search tree is a special type of tree in which the left subtree of a node contains only nodes with keys lesser than the node's key and the right subtree of that node will contain nodes with keys greater than the node's key. So for a balanced binary search tree we assume that we have a total of n nodes and both the left and the right subtrees can contain a maximum of n/2 nodes. For this case, if any node is tried to made the root than we have atmost n/2 rotations, which is obviously lesser than n-1.

Now consider the case where we are having unbalanced tree, say, left heavy or a right heavy tree. In both the cases, we have n nodes and a maximum of n-1 nodes are residing in the subtree (as node 1 is the root). So to make any node as the root in this case we would require at most n-1 rotations.

b. We can simply traverse the nodes in inorder traversal and can insert them one by one into a self-balancing binary search tree like AVL tree. This way can create a balanced binary search tree with at most O(n log n) rotations implying a time complexity of O(n log n).