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. In the question nI = internal nodes number, nE = number of external nodes.
To be proved: if every internal node in T has 3 children then nE=2nI +1
Let, this statement is true for lnodes (where l < n)
So, lE =2∗lI +1
Now, we increase the number of internal nodes by 1.
Hence, lInew = lI + 1.
Hence, lEnew = lE – 1+ 3 = 2∗lI +1 – 1 + 3 = (2mI + 2) + 1 = 2(lI + 1) + 1 = 2∗lInew +1
Thus in the same way it can be proved by method of induction when every internal
node of T has exactly 3 children then nE=2nI +1.
2. a)
Inserted data in first to last order: 2, 7, 3, 12, 5, 20, 14, 6, 11, 8, 15, 17, 1, 19, 23, 14
Min heap tree:
b) Binary Search tree is given below.

2ANSWER TO ASSIGNMENT 2
c) AVL tree: