20 votes 20 votes Consider the binary tree in the figure below: Give different steps for deleting the node with key $5$ so that the structure is preserved. DS gate1991 data-structures binary-tree normal descriptive + – Akash Kanase asked Apr 18, 2016 edited May 8, 2021 by gatecse Akash Kanase 3.5k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 21 votes 21 votes 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: ManojK answered Apr 19, 2016 edited Apr 17, 2021 by Lakshman Bhaiya ManojK comment Share Follow See all 15 Comments See all 15 15 Comments reply Show 12 previous comments tusharp commented Jan 14, 2019 reply Follow Share @rahul sharma 5 nice catch :) . 0 votes 0 votes ankit3009 commented Feb 2, 2021 reply Follow Share 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. 0 votes 0 votes Pranavpurkar commented Aug 11, 2021 reply Follow Share 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 ? 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes Sorry for orientation problem Rishi yadav answered Oct 4, 2017 Rishi yadav comment Share Follow See 1 comment See all 1 1 comment reply Kiyoshi commented Apr 25, 2021 reply Follow Share why you always have orientation problem... 2 votes 2 votes Please log in or register to add a comment.
0 votes 0 votes 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. Lakshman Bhaiya answered Apr 17, 2021 reshown Apr 17, 2021 by Lakshman Bhaiya Lakshman Bhaiya comment Share Follow See all 0 reply Please log in or register to add a comment.