edited by
4,391 views
20 votes
20 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.

edited by

3 Answers

Best answer
28 votes
28 votes
  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.

edited by
10 votes
10 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)

Related questions

27 votes
27 votes
2 answers
1
Arjun asked Dec 17, 2016
3,081 views
Write a constant time algorithm to insert a node with data $D$ just before the node with address $p$ of a singly linked list.
36 votes
36 votes
2 answers
4