Binary Trees

Definition: Binary Trees are rooted trees where each vertex has either $0$, $1$ or $2$ direct descendent edges associated with it.

For example, the following graph is a binary tree since each vertex has at most $2$ directed descendent edges associated with it.

Probability and Games

Binary trees appear often in elementary probability and games. For example, what is the probability that you will get $3$ heads in a row when flipping a single fair coin? We can answer this problem algebraically by knowing that the probability of getting a head once is $\frac{1}{2}$, so the probability of landing on heads three times in a row is $\left (\frac{1}{2} \right )^3 = \frac{1}{8}$. However, we can also illustrate this probability with a tree:

There are $8$ possible paths starting at the root of the tree, but only one path traverses $3$ red edges (representing landing on heads each time). So the probability of landing on heads $3$ times in a row with a fair coin is $\frac{1}{8}$.

Family / Ancestral Trees

Binary trees commonly appear in Family trees where the root of the tree is the earliest known ancestor of a family lineage. Each descendent in the family tree is associated to two parents, and so forth.