The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 votes

Consider the binary tree in the figure below:

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

asked in DS by Veteran (52k points) | 998 views
Is this a complete binary tree or almost complete binary tree??  For node 25 there is no left child...

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

4 Answers

+24 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 ->

  1. Search for element 5 using sequencial search in array.
  2. Swap it with last element in this case 27.
  3. 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.

answered by Boss (41k points)
edited by
+4 votes
I think given tree is min heap tree
answered by Boss (12.8k points)
+2 votes
a. Complete Binary Tree
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..
answered by Veteran (59.8k points)
0 votes

Complete Binary tree because 

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

reference -

answered by Boss (10.5k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,540 questions
54,100 answers
71,007 users