Register

Binary tree doubt

412 views
1 votes
1 votes

Q Consider a complete Binary Tree ‘T’ with key of root node be ‘P’. It is given that the left and right subtree of ‘P’ satisfies min-heap property. What is the time taken to convert the given tree ‘T’ to a max heap ?

1.O(log n)

2.O(n)

3. O(n log n)

4.Ο(n2)

User Avatar

1 Answer

3 votes
3 votes

The answer should be O(n). Since there is no better way to convert a min heap to max heap (or vice-versa) than to reconstruct the heap in O(n). Given additional features like left and right subtrees being min heap won't help either.

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
Na462 asked Jan 16, 2019
388 views
Binary tree
Consider a binary tree for every node | P - Q | <= 2. P represents number of nodes in left subtree of S and Q represents number of nodes in right subtree of S for h > 0. The minimum number of nodes present in such tree of height h = 4 ( Root at 0 level)
Consider a binary tree for every node | P - Q | <= 2. P represents number of nodes in left subtree of S and Q represents number of nodes in right subtree of S for h 0. T...
User Avatar
0 votes
0 votes
0 answers
2
Pawan Kumar 2 asked Dec 4, 2018
960 views
binary tree
Consider a binary tree, where for every node $P-Q\leq 2$.Prepresent number of nodes in left sub tree for node S and Q represents the number of nodes in right sub tree for node S for $h>0$. The minimum number of node present in such binary tree of height $h=4$ _____________ Im getting 8. kindly verify
Consider a binary tree, where for every node $P-Q\leq 2$.Prepresent number of nodes in left sub tree for node S and Q represents the number of nodes in right sub tree for...
User Avatar
0 votes
0 votes
0 answers
3
Soumya29 asked Oct 22, 2018
306 views
Binary Tree
I know the answer. But is there any general FORMULA for it? If yes, please provide the complete derivation of it. In the solution, they used $\rightarrow 2^{h-1}+1.$ I tried but I am not able to derive it.
I know the answer. But is there any general FORMULA for it?If yes, please provide the complete derivation of it. In the solution, they used $\rightarrow 2^{h-1}+1.$ I tri...
User Avatar
0 votes
0 votes
0 answers
4
Na462 asked Oct 20, 2018
621 views
Labelled Binary Tree
Consider 4 labeled 1,2,3,4. The number of distinct binary tree possible such that whose inorder traversal is 1,2,3,4 are ........
Consider 4 labeled 1,2,3,4. The number of distinct binary tree possible such that whose inorder traversal is 1,2,3,4 are ........
User Avatar
Link Copied!