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.