GATE CSE 1991 | Question: 14,b

Question

Consider the binary tree in the figure below:

Give different steps for deleting the node with key $5$ so that the structure is preserved.

Answer 1

Since the given binary tree is a min-heap tree.

• First swap $27$ and $5$
• Then delete $5$
• Apply min-heapify

And structure will be:

 

Comments

but deleting 1 is not told in question.

---

can we do first swap 27 and 5

And then delete 5 and apply minheapify

---

is this the correct answer for sure ?

---

ravi  do you have alternative than you can add here.

---

@ManojK,

No, not at the moment, I am yet to read Heaps properly. But I just wanted to know the general method when it comes to deleting a node in a Heap having 2 children. Like there are different ways to delete nodes with different no. children when it comes to BSTs.

---

We can use increase key operation where we can set the value of 5 to infinityO(1) and then apply minheapify down the pathO(log n) and then delete infinity O(1)

---

I think during first step, we should swap 5 and 17, not 27. Because in the subtree rooted at 5, the last element is 17. 27 is the last element in main heap. Correct me if I am wrong

---

@ ManojK is correct

First swap 27 and 5

Then delete 5

then heapify

https://webdocs.cs.ualberta.ca/~holte/T26/heap-del.html

---

is this correct method for solving this que ???   cant we replace 5 by its inorder successor or predecessor and after that min hepify the tree  ???

---

@ itsvkp1 no you can't,that will be applicable to only BST not in a heap.

---

@achitjindal07

If you swap 17 and 5, and then delete instead of swapping 27 and 5. Then it is not correct because structure property of heap that is "All the level of heap should be completely filled except the last level and the last level should be left filled" is violated.

---

25 has right child but not left,it is not complete tree.It cannot be min heap.I think there is some mistake in question?

---

@rahul sharma 5 nice catch :) . 

---

Yes it is not almost complete binary tree, so not min heap too. To satisfy the min heap, it must be almost complete binary tree.

---

25 has right child but not left,it is not complete tree

It is ACBT that’s why min heap possible but i am confused that can we delete 5 in min heap i mean in min heap always the root is deleted by default and we can’t delete from the middle of the tree bcoz then it will not remain ACBT and thus not min heap!

so my doubt is how can we directly delete 5 in min heap without deleting the root 1 ?  

Answer 2

Sorry for orientation problem 

Comments

why you always have orientation problem...

Answer 3

Assuming that we have stored this heap in an array structure, Procedure: 

• Search for element $5$ using the sequential search in the array.
• Swap it with the last element, in this case, $27.$
• Bubble down it so that the min-heap property is satisfied.