The Gateway to Computer Science Excellence

+16 votes

Consider the binary tree in the figure below:

(a). What structure is represented by the binary tree?

0

Is this a complete binary tree or almost complete binary tree?? For node 25 there is no left child...

0

@garl

Almost complete BT as in complete BT nodes should be as right as possible and all levels filled except the last one.

Almost complete BT as in complete BT nodes should be as right as possible and all levels filled except the last one.

+27 votes

Best answer

**(A)** This is min heap. It is obvious looking at tree.

**(B) **Assuming that we have stored this heap in array structure, Procedure ->

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

**(C)** Deleting element from mean heap , O(logn) , but for searching in Heap we need O(N)

So, time complexity of sequencial search + Delete = > O(N) + O(logN) = O(N).

We cant use binary search as it is heap.

+1

@idontknowwho

This is not a min heap as the tree is not complete . 27 should be on left . Then the answer holds

+2 votes

a. Complete Binary Tree

c.

let Node A has to b deleted.

1. Find deppest node as well as selection of deepest node which preserve structure..

2. overwrite A data with deepest node data.

3. delete deepest node.

b. finding deepest node is crucial here .. in this case 5 will be overwritten by 27.. then delete 27..

c.

let Node A has to b deleted.

1. Find deppest node as well as selection of deepest node which preserve structure..

2. overwrite A data with deepest node data.

3. delete deepest node.

b. finding deepest node is crucial here .. in this case 5 will be overwritten by 27.. then delete 27..

+1 vote

Complete Binary tree because

A **complete binary tree** is a**binary**** tree** in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

reference - http://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html

52,345 questions

60,513 answers

201,930 comments

95,354 users