retagged by
5,747 views
5 votes
5 votes
What is the worst case time complexity to construct an AVL tree from an array which satisfies the min heap property ?

a) O(n log n)

b) O(n2)

c) O(n2 log n)

d) O(n)
retagged by

4 Answers

7 votes
7 votes
Elements are present in array which satisfies min heap property so we have to take element from array and construct the AVL tree one by one.

Deletion of element from given array takes O(log n) time because it is min heap and for insertion in  AVL worst case will be O(log n) time .

For n elements Total time= O(nlogn) + O(nlogn) = O(nlogn)
1 votes
1 votes
The array is given which satisfies Min-Heap property.

We will sort the array using any sorting which takes minimum time i.e. nlog n.

Now we recursively compute mid = (start+last)/2;

and make the element A[mid] as the root and call the same recursive function on left and right part.

AVL tree will be constructed in n.log n time.
1 votes
1 votes

A. O(nlogn)

For n elements, whatever the given sequence of these elements be (sorted, reverse sorted, unsorted, min/max heap,etc), AVL creation time will be same as creation procedure does not depends upon the sequence of input elements.

0 votes
0 votes
array is given which satisfies min heap

we will built the tree from the array which takes O(n) time then balancing of the node will take O(logn) time as rotation takes O(1) time to built the AVL and in worst case we can do O(logn) rtation

Related questions

5 votes
5 votes
1 answer
1
junaid ahmad asked Dec 19, 2017
1,999 views
Which of the following is highest upper bound that represents the time complexity of inserting an object into AVL tree with n-nodes.It must be 0(logn) right.What would be...
1 votes
1 votes
0 answers
2
Chaitanya Kale asked Oct 9, 2022
391 views
Given a skew tree what will be the time complexity to balance the tree? What will be the algorithm for this?
0 votes
0 votes
1 answer
3
Arnabi asked Jan 28, 2017
725 views
2 votes
2 votes
2 answers
4
Akriti sood asked Dec 21, 2016
663 views
can anyone define the procedure to find the common ancestor of any two given nodes in balanced BST..??