The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+12 votes
784 views
  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 (59.6k points)
edited by | 784 views
0

Similar question for part A: https://gateoverflow.in/2313/gate1993-16  Digvijay Pandey Sir's answer

2 Answers

+16 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$
    $0+1=1$
    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 $\leq 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
    $2F+2=2L$
    $2(F+1)=2(L)$
    $\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 Boss (22.9k points)
edited by
+3
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.
0
why are you not using build method to create heap ? here nothing is mention
+1
Draw the min-heap that results from insertion of the following elements in order into an initially empty min-heap

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

Hope this helps.

0
Thanx a lot...
0
yes your solution really helps..
+7 votes

Part(a) 

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 (61k points)
0
how did you draw min heap drawn  below one is correct one

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

41,053 questions
47,651 answers
147,210 comments
62,380 users