in DS edited by
2,578 views
21 votes

Consider the binary tree in the figure below:

What structure is represented by the binary tree?

in DS edited by
2.6k views

4 Comments

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.
1
@gari yeah it should to left of 25..in almost complete binary tree a node can have one child only in last level and in last level nodes must be filled from left to right..
0
but this is not a complete binary tree right?
0

Subscribe to GO Classes for GATE CSE 2022

3 Answers

29 votes
 
Best answer
This is min-heap. It is obvious looking at the tree.
We cant use binary search as it is a heap.
edited by

6 Comments

@idontknowwho

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

2
edited by
A min heap is almost complete binary tree. This is not a min heap as it is  not almost complete.
0
This is not a min heap. Leaves should be filled from left to right. If 27 were a left child, then this tree would be min heap. Write this tree as an array and use formula (2i + 2) for 25’s right child index. You won’t get 27 as answer but this tree has 27 as right child. (Assuming indices start from 0 and i is 25’s index)
1
yes. corected
0
See, this is a heap only

27 is the left child

Due to space issue, the image is misleading, but its your responsibility to assume it almost complete

The tree is a min heap only
0
Unless someone has an original image from the 1991 paper, I can’t comment more. From the question’s image, 27 is definitely the right child.
0
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..
2 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 - http://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html

Related questions

Ask
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