# Time complexity for balancing an unbalanced binary tree

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.

• Is initial tree a BST? – HEKTO Sep 12 '19 at 18:59
• @HEKTO In the question it was just written "n-node unbalanced tree". It was not mentioned to be a BST. I assumed it would be a BST. – Siladittya Sep 12 '19 at 19:03
• There is DSW algorithm to balance a BST - please look in Wikipedia – HEKTO Sep 12 '19 at 19:08

• 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.