# Prove that the number of full nodes plus one is qual to the number of leaves in a nonempty binary tree

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.

• 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? – collapsar Feb 17 '18 at 9:01

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.