Binary Tree

A tree with each node consisting of at most two children

Height

• Max: $N-1$ (spindly)
• Min: ${\log }_{2}N$ (bushy)
• Average: $O(\sqrt{N})$
• We want bushy trees because they are more efficient

Categories

• Full
  • All nodes have either 2 children or 0 children (leaf nodes)
• Perfect
  • Full binary tree of height $h$ with exactly $2^h-1$ nodes ($h$ is 1-based)
  • Means every branch goes all the way to the end of the tree
  • $n$ nodes → $\lceil {\log }_{2}n\rceil$ height
  • Implies complete and full (but not visa versa)
• Complete
  • A perfect binary tree through level $h-1$ with some extra leaf nodes at level $h$
  • Extra nodes are filled from left to right
  • $n$ nodes → $\lceil {\log }_{2}n\rceil$ height
• Binary Search Tree