Time complexity for balancing an unbalanced binary tree

Question

The question here is that: There is an unbalanced binary tree with n-nodes. What is the time complexity to balance the tree?

The solution I thought of involved solving using Recursion where for the worst-case I took a maximally unbalanced tree like this

And then try to balance this using rotations.

But I cannot come up with an expression which will give O(log(n)) time complexity.

Can I get some help in solving this? I am stuck on how to approach this problem.

Answer 1

Do an inorder traversal of the BST...and store it in an array the array will be sorted. next construct a balanced binary search tree from this array. 1) Get the Middle of the array and make it root. 2) Recursively do same for left half and right half. a) Get the middle of left half and make it left child of the root created in step 1. b) Get the middle of right half and make it right child of the root created in step 1.

Time Complexity of both inorder traversal and AVL tree construction is O(n).

Answer 2

I don't think that it is possible to balance a tree in logarithmic time:

• An algorithm has to determine somehow, when it is finished
• In this case, establishing that the tree is balanced is necessary
• This operation alone is $\mathcal O(n)$ (count the height of left/right subtree)

Therefore, $\mathcal O(n)$ will be a lower bound for your algorithm and there are multiple ways to construct binary trees in linear time, so take either one of them.