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

asked in DS by Boss (8.7k points)   | 102 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 (66.5k points)  
edited by


Top Users Jun 2017
  1. Bikram

    3820 Points

  2. Arnab Bhadra

    1526 Points

  3. Hemant Parihar

    1502 Points

  4. Niraj Singh 2

    1491 Points

  5. Debashish Deka

    1440 Points

  6. junaid ahmad

    1432 Points

  7. pawan kumarln

    1278 Points

  8. Rupendra Choudhary

    1242 Points

  9. rahul sharma 5

    1240 Points

  10. Arjun

    1228 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 26 - Jul 02
  1. pawan kumarln

    410 Points

  2. akankshadewangan24

    282 Points

  3. Arjun

    268 Points

  4. Abhisek Das

    230 Points

  5. Debashish Deka

    194 Points


23,428 questions
30,143 answers
67,576 comments
28,472 users