GATE CSE 1999 | Question: 12

Question

• A. 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.

• B. 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.

Comments

Best & easy link to learn Mathematical induction

 https://www.mathsisfun.com/algebra/mathematical-induction.html

https://courses.cs.washington.edu/courses/cse373/00sp/solutions/hw2-457.txt

---

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

---

@Rajesh Pradhan Thanks a lot , was like I hate induction proving type questions, but now very clear with it.

 

Answer 1

1. Note My Convention:-
   Number of full nodes $=F$
   Number 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 $\leq 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.
   Please refer the below image where 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.

Comments

@Pinaki Dash

This is actually what i need.

Thank you !

---

And i must say who so ever is having doubt in above picture that why we always have a tendency to fill left child first then the answer is - Both min heap and max heap works like complete binary tree. 

 

---

I am confused on 2nd part.. 

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,17,6,5,4,3,2,1. Show the result after the deletion of the root of this heap.

which case to apply both of them correct and give minheap accordingly.

case 1: Either first create the whole tree by insertion and then apply heapify.

this will result in to minheap whose level order traversal (BFS) is 1 3 2 4 6 7 5.

by removing the root and heapify gives BFS traversal as : 2 3 5 4 6 7

 

case 2 : apply heapify after every element/node insertion in the tree.

this will result in to minheap whose level order traversal (BFS) is 1 4 2 7 5 6 3.

by removing the root and heapify gives BFS traversal as : 2 4 3 7 5 6.

In above 2nd method is applied.

Answer 2

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)

Comments

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

Answer 3

obtion b