Trees

a connected graph with no cycles

all vertices have a possible path between them
a tree $G = (V, E)$ with $| V | \geq 2$ must have at least 2 vertices with degree 1 (leaf)
- proof: need 2 dead-ends otherwise the tree will have a cycle
$| E | = | V | - 1$

Forest

a graph with no cycles
each component of a forest is a tree

Leaf

a vertex of degree one
the end of each branch of the tree

Binary tree

a tree where each vertex has degree at most 3
balanced binary tree is a tree where the height of any two vertices is not different by more than 1
- height = length from root to leaf

\begin{matrix} \frac{(\binom{2 p}{n}) n^{2 p - n}}{n^{2 p}} = (\binom{2 p}{n}) n^{- n} = \frac{2 p!}{n! (2 p - n)!} n^{- n} = \end{matrix}