Full binary tree with $L$ leaves has $2L - 1$ total nodes
Definition of Full Binary Tree A Binary Tree is full if and only if every node has 0 or 2 children. Proof by Induction Inductive Hypothesis The full binary tree with $L$ leaves has $N = 2L - 1$ total nodes. Base Case We can easily think of two base cases. Note that the shape of the tree at each base case is unique (Draw by yourself). If L = 1, then N = 1. If L = 2, then N = 3. Inductive Step We want to show that the full binary tree with $L + 1$ leaves has $2(L + 1) - 1$ total leaves $\forall n \gt 2, n \in \mathbb{N}$. Suppose that $\exists n \gt 2, n \in \mathbb{N} $ the full binary tree with $L$ leaves has $2L - 1$ total leaves. $T$ : the full binary tree with $L$ leaves. $v$ : a leaf node of $T$ If we want to append a new node in $T$, two nodes must be inserted on the left and right side of some leaf node of $T$. Which implies that every node insertion increases $N$ by $2$ and $L$ by $1$. $2L - 1 + 2 = 2(L + 1) - 1$ Hence, t...