0
$\begingroup$

How to prove

In a tree where every node has either $0$ or $2$ children, the number of nodes with $0$ child is $1$ more than the number of nodes with $2$ children.

$\endgroup$

1 Answer 1

3
$\begingroup$

This can be proven by induction. What you describe is a Full binary tree, and it has a convenient induction definition:

  • a single node (or leaf) is a full binary tree;
  • a tree with two children that are full binary trees is a full binary tree.

This permits a structural induction proof of the property you want:

  • prove that it is true for a single node tree;
  • suppose that it is true for two full binary trees $a$, $b$, then prove that it is true for the node $N(a, b)$ with $a$ and $b$ as children.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.