edited by
2,950 views
31 votes
31 votes

Consider the binary tree in the figure below:

Outline a procedure in Pseudo-code to delete an arbitrary node from such a binary tree with $n$ nodes that preserves the structures. What is the worst-case time complexity of your procedure?

edited by

2 Answers

Best answer
61 votes
61 votes

By looking at the values it is clear that It is a Min-Heap Data structures. We know that Heap Data structures are stored in the array.

$\implies $ Delete procedure for Min-Heap Data Structure (If you already know the value and position of the node):

  1. Replace that node with the last element of that tree.
  2. Apply Heapify property on that node.

For Example, Let If I want to delete $1$, then I will replace that with $27$. and apply heapify on that node. Or if i want to delete $5$ then also I will replace that with $27$, and apply heapify on that node.

Time Complexity: In this case, time complexity will not be more than $O(\log n)$.

$\implies $ Delete procedure for Min-Heap Data Structure (If you know the value but not position) :

  1. Find the position of the number by sequential search. (In the worst case it will take $O(n)$ time).
  2. Replace that node with the last element of that tree.
  3. Apply heapify property at that node. 

Time Complexity: Wort time complexity of this algorithm will be $\mathbf{O(n + \log n)}$ i.e. $\mathbf{O(n)}$.

Note: This is a standard problem of Minimum element deletion from the Min-heap tree. The minimum element always resides at top (Root node). We just replace that value with the last element of the tree and apply heapify at the root node. The time complexity of that algorithm is $\mathbf{O(\log n)}$. 

Here I have written the second method only to show that if we have to delete any of the nodes, and we just know the value but not the position. Since in question it is mentioned that Arbitrary node

edited by
4 votes
4 votes
Deleting an element from the min-heap, $O(\log n),$ but for searching in Heap we need $O(N).$

So, time complexity of the sequential search $+$ Delete $\implies O(N) + O(\log N) = O(N).$

Related questions

25 votes
25 votes
3 answers
1
Kathleen asked Sep 12, 2014
4,249 views
Consider the binary tree in the figure below:What structure is represented by the binary tree?
20 votes
20 votes
3 answers
2
Akash Kanase asked Apr 18, 2016
3,451 views
Consider the binary tree in the figure below:Give different steps for deleting the node with key $5$ so that the structure is preserved.
44 votes
44 votes
2 answers
3
Kathleen asked Sep 12, 2014
13,565 views
The weighted external path length of the binary tree in figure is ______
20 votes
20 votes
5 answers
4
Kathleen asked Sep 12, 2014
5,375 views
If the binary tree in figure is traversed in inorder, then the order in which the nodes will be visited is ______