Definition. A full binary tree $($FBT$)$ is one of:

$-[]($a single node$),$ or

$-[$T$1,$ T$2],$ where T$1$ and T$2$ are FBT$$s $($two trees joined together with one new root

and two new edges from the new root to the old roots of T$1$ and T$2)$

We can define a recursive function nd: FBT $N$ that counts the number of nodes in a FBT as follows:

$nd(T)=\{\begin{array}{ccc}1& if& T=[]\\ nd(T_1)+nd(T_2)+1& ifT=[T_1,T_2]\text{f}\text{o}\text{r}FBT\text{'}s{T}_1\text{a}\text{n}\text{d}& T_2\end{array}$

$($a$)$ Write a recursive definition of the function ed : FBT $N$ that calculates the

number of edges in a tree.

$($b$)$ Using your definition of ed$,$ prove the following claim using structural induction:

Claim. For every full binary tree $t,nd(t)=ed(t)+1.$