The set of full binary trees is defined recursively by:
• Basis step: There is a full binary tree consisting of a single vertex $r$.*
• Recursive step: If $T_1$ and $T_2$ are disjoint full binary trees, then the tree $T = T_1 \cdot T_2$ formed by connecting a new root $r$ to each of the roots of the left subtree $T_1$ and right subtree $T_2$ is also a full binary tree.
a) Give recursive definitions of the functions $n(T)$ and $l(T)$ which count the number of vertices and the number of leaves, respectively, in a full binary tree.
b) Prove that $n(T) = 2l(T)−1$ for all full binary trees $T$, using structural induction.
Could anyone verify that my answere is correct?
My answer;
The property can be proof using induction.
Induction basis step: There is a full finary tree consisting of a single vertex $r$. That vertex $r$ also a single leaf node,
Therefore, $l(T) = 1$. Now, $n(T) = 2l(T) - 1 = 2\cdot 1 - 1 = 2 - 1 = 1.$ Hence the propery is true for a single node.
Recursive step: If $T_1$ and $T_2$ are disjoint full binary trees of same height h, then the tree $T = T_1\cdot T_2$ formed by connecting a new root node r to each of the roots of the left subtree $T_1$ anf right subtree $T_2$ is also a full binary tree of height h+1. Now assume that the property is true for $T_1$ and $T_2$.
Therefore, $T_1$ and $T_2$ both have $n(T)$ number of vertices and $l(T)$ number of leaves. Now after form a new binary tree, the number of vertices are: $n(T) + n(T) + 1$ [ $1$ for newly root node]. Total $2n(T) + 1$ verices. And the new binary tree contains, $l(T) + l(T)$ number of leaves. In Total $2l(T)$ number of leaves.
Now, $2n(T) + 1 = 2[2l(T)] -1] + 1$ [ since $n(T) = 2l(T) - 1$ is true for $T_1$ and $T_2$]
or $4l(T) -2 +1$
or $4l(T) -1$
or $2\cdot 2l(T) - 1$
The newly binary tree contains $2l(T)$ number of leaves. Hence proved.
I think you would like to highlight that because you are working with full binary tree and hence $T_1$ and $T_2$ must have the same height. Also, in the middle of your solution, the index for $T_1$ and $T_2$ are dropped, which is confusing. Thoughour the induction process, we deal with $3$ full binary trees, $T$, $T_1$, and $T_2$.
We assume the conjecture is true for full binary tree of depth $k$, $T$ and now we are given a tree with depth $k+1$, $T$. We note that $T$ consists of the root and the left subtree of depth $k$, $T_1$ and right subtree $T_2$ of depth $k$.
We know that $T$ consists of $T_1$ and $T_2$, and they are linked by the root. Hence, $n(T)=n(T_1)+n(T_2)+1$.
Also, the leavess of $T$ are the leaves of $T_1$ and $T_2$, hence $l(T_1)+l(T_2)$.
By our induction hypothesis, we know that $$n(T_1)=2L(T_1)-1$$
$$n(T_2)=2L(T_2)-1$$
Hence, \begin{align}n(T)&=n(T_1)+n(T_2)+1 \\ &= (2l(T_1)-1) + (2l(T_2)-1)+1\\ &=2(l(T_1)+l(T_2))-1\\ &= 2l(T)-1\end{align}