Answer to Assignment 2

Running head: ANSWER TO ASSIGNMENT 2
ANSWER TO ASSIGNMENT 2
Name of the Student
Name of the University
Author Note

1ANSWER TO ASSIGNMENT 2
1. It is given that nI is the number of internal nodes and nE is the number of external
nodes. Now, it is needed to be found that if each internal node in T has 3 children then
nE=2nI +1.
Now, let the statement is true for m nodes (m < n)
Hence, mE =2∗mI +1
Now, let the internal nodes is increased by 1.
Hence, mInew = mI + 1.
Hence, mEnew = mE – 1+ 3 (as with the increase of each external nodes 3 internal nodes
are increased excluding the external node).
= 2∗mI +1 – 1 + 3 = (2mI + 2) + 1 = 2(mI + 1) + 1 = 2∗mInew +1
Now, in the similar way extending the result by method of induction it can be shown
that if every internal node of T has exactly 3 children then nE=2nI +1.
2. a)
The heap min binary tree after insertion of 2, 7, 3, 12, 5, 20, 14, 6, 11, 8, 15, 17, 1, 19,
23, 14 is shown by the following tree.
Min heap tree:

2ANSWER TO ASSIGNMENT 2
b) Binary Search tree is given below.