Structural induction on binary tree: full and crooked

Question

I have no idea where to start on this structural induction question, please help me out with a thorough explanation!

Answer 1

Let $P(T)$ be the statement "The tree $T$ is a not a full crooked binary tree". We want to show that $P(T)$ holds for all trees.

Notice that trees themselves can be defined recursively. To show that $P(T)$ holds for all trees $T$, we first need to show that it holds for the base case: the empty tree. It is clear that the empty tree is not a full crooked binary tree.

Next, we move on to the (structural) inductive step. Consider a non-empty tree $T$. By the recursive nature of trees, this tree must have a left and right subtree $T_L$ and $T_R$. Our (structural) inductive hypothesis will be that $T_L$ and $T_R$ are not full crooked binary trees and we will show from this that it must also be the case that $T$ is also not a full crooked binary tree. This will be enough to prove $P(T)$ for all trees $T$.

Since $T_L$ is not a full crooked binary tree, it is either not a full binary tree or it is not a crooked binary tree. We consider both cases.

1. In the case that $T_L$ is not a full binary tree, then by the definition of full binary tree, $T$ is also not a full binary tree since the definition requires both subtrees to be full binary trees. Since $T$ is not a full binary tree, it is also not a full crooked binary tree.

2. Consider the case where $T_L$ is not a crooked binary tree. Notice that $T_R$ is also not a full crooked binary tree, so it either not a full binary tree or it is not a crooked binary tree. We consider both cases again.

   a. In the case that $T_R$ is not a full binary tree, then $T$ is not a full crooked binary tree by the same reason as case 1.

   b. In the case that $T_R$ is not a crooked binary tree, now we have that both subtrees of $T$ are not crooked. Thus, by the definition of crooked binary trees, $T$ is also not a crooked binary tree. Since $T$ is not a crooked binary tree, then it also cannot be a full crooked binary tree.

---

Since we have showed both the base step and the structural inductive step for $P(T)$, it holds that $P(T)$ holds for all trees.