88 views

### My main doubt is - will it O(n) time to reach to leaf nodes?

asked in DS | 88 views
0
max heap tree is given, so no need to check max heap property again

$O(logn)$ will be sufficient
0

@srestha  Time taken to find the leaf node?

+1
To find that particular leaf element O(n)

To maintain heap property O(log n)

Total O(n)
0

Tesla! Thanks buddy! and thank you srestha Ma'am.

+1

### we want to delete any of the leaf node

$O(1)$ will suffice for deleting any leaf node(If you are asked to delete any leaf node and not some specific leaf node)...Just delete the last element.

Heap is nothing but an array with heap property. So If you wish to delete just $any$ leaf node, then Just delete the last element of the Heap and it will take just $O(1)$ time since It is an array and you can go to the last element in $O(1)$ time.
selected by
0
And how about a particular leaf node apart from last leaf node?
0
previous of last node , is also a leaf node
0

And how about a particular leaf node apart from last leaf node?

There are approx $\frac{n}{2}$ leaves in the Heap. So, If we wish to delete some Specific leaf node then first we would have to find it, which could take $O(n)$ time itself. Then after finding that leaf we can delete that node in just $logn$ time.

0

previous of last node , is also a leaf node

Wouldn't be true if $n=2$

0
then also $O(1)$ if $n=2$

if $n>2$ then too $O(1)$
0

There are approx n2 leaves in the Heap. So, If we wish to delete some Specific leaf node then first we would have to find it, which could take O(n) time itself. Then after finding that leaf we can delete that node in just logn time.

So, it's O(n) * O (logn) = O(n), right?

1
+1 vote
2
+1 vote