Here is a recursive definition for some set $T$ of non-empty binary trees.

  • A single node is in $T$
  • If $t_1$ and $t_2$ are in $T$, then the bigger tree with root $r$ connected to the roots of $t_1$ and $t_2$ is in $T$

Use structural induction to prove the following property of the elements of $T$: there are $m$ nodes that have two children and $m+1$ nodes that have no children.

Context: I am in a theory of computation class after taking 1.5 years off school and we are on (structural) induction proofs. I never really had trouble with weak/strong induction, but this one is harder for me to grasp, probably because it has recursive definitions and trees.

I really need help with these as I have a midterm soon and I can't do any of these homework problems. Can anyone please show me how they would do this? What would you do in order to guarantee full marks on a test?


Basis : the single node tree $t$ has $0$ nodes with two children, and $1$ node with no children.

Thus : $m=0$ and $m+1=1$.

Induction step : assume that $t_1$ is a tree with $m_1$ as in the hypoteses and $t_2$ a tree with $m_2$.

The new tree $t$ is formed adding root $r$ having as children the roots of $t_1$ and $t_2$.

We have to calculate "his" number $m_t$.

The new tree $t$ has one more node with two children (the root $r$).

Thus it has :

$m_1+m_2+1$ nodes with two children and this is the $m_t$ of the new tree $t$.

The number of nodes with no children is left unchanged, and is the sum of the numbers of $t_1$ and $t_2$, i.e. : $m_1+1$ and $m_2+1$.

Thus :



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.