Question $1$

$($a$)$ If a Binary Tree is either empty or is a node with a left child and a right child that are both Binary Trees, what additional conditions must a Binary Tree satisfy for it to be

$($i$)$ Complete, and

$($ii$)$ a Binary Heap Tree?

$[4$ marks$]$

$($b$)$ The items $6,9,4,8,12,5$ need to be inserted one at a time into a Binary Heap Tree, starting from an empty tree. Show the state of the tree after each item has been inserted.

$[6$ marks$]$

$($c$)$ One approach for sorting an array of items, $a,$ is to first insert them into a Binary Search Tree, $t,$ and then output them back into the array in order. Write, in pseudocode, a recursive procedure for filling the array from the Binary Search Tree, and specify what the initial call of the procedure is$.$ You may call any of the standard primitive operators for binary trees

$[10$ marks$]$