933 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.

edited | 933 views
0

Similar question for part A: https://gateoverflow.in/2313/gate1993-16  Digvijay Pandey Sir's 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.

edited
+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..
+11

Hope this helps.

0
Thanx a lot...
0
0
Yes it works... Thanks!

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)

0
how did you draw min heap drawn  below one is correct one

1
2