Tree Properties

Some fundamental properties of trees: A tree with $n$ nodes has exactly $n - 1$ edges. Each node except the root has exactly one incoming edge from its parent.

A binary tree can be unbalanced. In the worst case (a "stick"), height equals $n - 1$. In the best case (perfect balance), height is $\lfloor \log_2 n \rfloor$.

For a complete binary tree stored in an array (index starting at 0):

• Parent of node $i$: $\lfloor (i-1)/2 \rfloor$
• Left child of node $i$: $2i + 1$
• Right child of node $i$: $2i + 2$

This array representation is how heaps work. You'll return to it later.