GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
129 views

asked in DS by Boss (9.1k points) 4 64 210 | 129 views

1 Answer

+4 votes

Almost Complete Binary Tree is Complete Binary Tree In Which Last Level Strictly Is Not Full

A complete binary tree is one in which:

a) All levels of the tree (except last level possibly) are full..

b) The nodes in the last level  are arranged in a left to right manner..

So as we have said that last level is not full necessarily..So this means the child pointers of some of the earlier level nodes will also remain empty and hence they will be leaf nodes as well.

Hence a leaf node can be either in the last level or 2nd last level.Hence statement (i) is true..

Now coming to the second statement , it uses the second property that is mentioned for this type of tree..It is saying about right descendents of a given node which is present in the last level , so this means say this right descendent is at the position 10 with respect to left most node in the last level..So compulsorily the left descendent of that particular node will be at less than 10th position w.r.t left most node of last level will be present in the almost complete binary tree..So consequently the left descendent of which we are talking about will be any of these nodes in the last level and hence at depth d..

Hence statement (ii) is true as well.

Hence C) is the correct option..

answered by Veteran (89.3k points) 15 58 296
edited by


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
Top Users Oct 2017
  1. Arjun

    23678 Points

  2. Bikram

    17278 Points

  3. Habibkhan

    8960 Points

  4. srestha

    6450 Points

  5. Debashish Deka

    5478 Points

  6. jothee

    5128 Points

  7. Sachin Mittal 1

    4882 Points

  8. joshi_nitish

    4486 Points

  9. sushmita

    4032 Points

  10. Rishi yadav

    3974 Points


Recent Badges

Notable Question Sedhu Raman
Notable Question cse23
Notable Question vishwa ratna
Notable Question learner_geek
Popular Question Devshree Dubey
Popular Question nish kim
Popular Question Simar sandhu
Popular Question Rashi Gupta
Notable Question Akriti sood
Popular Question Samujjal Das
27,407 questions
35,256 answers
84,505 comments
33,480 users