1
$\begingroup$

I'm trying to write an induction statement to prove a full node in a tree but I have no idea how to do that. I've always been terrible when it comes to logic. Where do I even start with this?

I know that a full node has 2 children.

$\endgroup$
1
  • $\begingroup$ Consider an arbitrary binary tree with n nodes. Where could you attach a n+1-th node? What would be the effect on the node counts? $\endgroup$ – collapsar Feb 17 '18 at 9:01
4
$\begingroup$

Well, an induction proof consists of a base case and an induction step. For trees that is usually structural induction, based on inductive ways trees are built.

The base case considers the smallest binary tree, which cannot be composed further. Show that one has the Property.

The induction step argues that the Property is true for any tree $T$ assuming the Property holds for its subtrees $T_{\textrm{left}}$ and $T_{\textrm{right}}$. That assumption is called the induction hypothesis.

There is another approach, induction based on the number of (full) nodes, called natural induction. Base case has a single full node. Induction step argues Property is true assuming Property holds for any tree having less full nodes.

$\endgroup$

Your Answer

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