The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+12 votes
  1. In binary tree, a full node is defined to be a node with $2$ children. Use induction on the height of the binary tree to prove that the number of full nodes plus one is equal to the number of leaves.

  2. Draw the min-heap that results from insertion of the following elements in order into an initially empty min-heap: $7, 6, 5, 4, 3, 2, 1$. Show the result after the deletion of the root of this heap.


asked in DS by Veteran (69k points)
edited by | 556 views

2 Answers

+13 votes
Best answer
  1. Note My Convention:-
    no. Of full node$=F$
    no. Of leaf node$=L$
    Base Case: $H = 0$.
    A binary tree of height $0$ is just a single node with no children, and therefore has $1$ leaf.
    $F+ 1 = L$
    so the base case satisfies the induction hypothesis (see below).
    Induction Hypothesis$(I.H)$: Suppose that for some $k \geq 0$, all binary trees of height $<= k$ have $(F +1 )= L$ leaves .
    Induction Step: Let T be a binary tree of height $k+1$. Then T's left and right subtrees are each binary trees of height $<= k$, and thus by the $I.H.$ both subtree have $(F +1)$ leaves. The number of leaves in $T$ is equal to the sum of the number of leaves in $T$'s subtrees,
    $(F+1)$left sub tree $+ (F+1)$right sub tree $= L$left sub tree  $+L$right sub tree
    $\large \therefore F+1=L$ (proved)

     Hence the hypothesis holds for $k+1$, and so the theorem is proved.
  2. Here in question they mentioned to insert element in given order into an empty Heap.
    So here we have to use Insertion Method to create the heap instead of using Heapify Method to build the heap.
    Plz refer below img the LHS shows the resultant  heap after doing insertion of the keys into initial empty  heap.
    RHS heap is the result of deletion of root.

answered by Veteran (23.4k points)
edited by
In part (A) why have you not considered that root node will also be a node with degree 2.

You just took into consideration the left and the right subtrees.
why are you not using build method to create heap ? here nothing is mention
Draw the min-heap that results from insertion of the following elements in order into an initially empty min-heap

Because of this
its not correct min heap
It is correct. Try inserting the elements one by one in the given order, you will get the same.
atleast show how it is done... m not getting correct answer..

Hope this helps.

Thanx a lot...
+7 votes


Base case: h=1 There is only one such tree with one leaf node and no full node. Hence the statement holds for base case.

Inductive step: h=k+1

Case 1: root is not a full node.

we assume it does not have a right child. In this case the number of full nodes and the the number of leaf nodes is equal to the tree which is rooted at at's left child. Since the height of that left subtree is k, by induction the difference should be 1.

Case 2: root is full node.

Total number of leaf nodes = number of leaf nodes in left + number of leaf nodes right subtree.

Total number of full nodes = Root (1) + the number of full nodes to its left and right.

Thus the difference remains 1.


Part (b)

answered by Veteran (60.4k points)
how did you draw min heap drawn  below one is correct one

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

33,705 questions
40,253 answers
38,862 users