0
$\begingroup$

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

enter image description here

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.

$\endgroup$
  • $\begingroup$ Is initial tree a BST? $\endgroup$ – HEKTO Sep 12 '19 at 18:59
  • $\begingroup$ @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. $\endgroup$ – Siladittya Sep 12 '19 at 19:03
  • $\begingroup$ There is DSW algorithm to balance a BST - please look in Wikipedia $\endgroup$ – HEKTO Sep 12 '19 at 19:08
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.