$($a$)$We consider rooted binary tree. A leaf node is a node which does not have any children nodes. The height of a binary tree is defined as follows:

The height of an empty tree is defined as $0.$ For a non$-$empty tree, the height is defined as the number of nodes in the path from the root to its farthest leaf node.

$($i$)$ Give a recursive definition for the height of a binary tree. $(5$marks$)$

$($ii$)$Based on $($i$),$ give a recursive algorithm, in pseudocode format, for accepting an input binary tree, and returning its height. $(4$ marks$)$

$($iii$)$Analyze the time complexity of your algorithm in $($ii$).(4$ marks$)$

$($b$)$ A programmer uses the following struct for constructing a rooted binary tree.

struct node $\{$

int x;

node$*$ left;

node$*$ right;

$\}$;

Inside a node, x is the stored data, left and right are pointers pointing to the node$$s left and right children, respectively, if any. If a pointer is not pointing to any node, it is called null pointer$($because$,$ the programmer should have assigned

it to NULL$).$

Suppose that an n$-$node binary tree is constructed using the above struct.

Using induction on n$,$ prove the following statement, for all integers n $>=1.$

Statement: An n$-$node binary tree has n$+1$ null pointers.

$(10$ marks$)$

$[$Hint: The proof should contain base case, and inductive step.$]$

$($c$)$ A student extends the struct in $($b$)$ into the following struct for constructing a rooted N$-$ary tree.

struct node $\{$

int x;

node$*$ child$[$N$]$;

$\}$;

As the struct in $($b$),$ variable x is the stored data, the pointers are pointing to children nodes, respectively, if any. If a pointer is not pointing to any node, it is a null pointer.

What is the number of null pointers in an n$-$node N$-$ary tree, in terms of n and N$?$

$(2$ marks$)$

$[$Hint: no need to explain.$]$