Terminology

Learn all these terms:

• subtree
• edge
• parent
• path
• path length
• ancestor
• descendent
• depth
• height
• level
• leaf
• internal
• full
• complete

The Wonder and Joy of Binary Trees

• We will spend a lot of time thinking about binary trees.
• Why????
• Question for you:
  • What is the maximum number of nodes in a binary tree of height $h$?
  • $N(h) \leq ??$

  $\displaystyle\sum_{i=1}^n c = cn$	$\displaystyle\sum_{i=1}^n i = \displaystyle\frac{n(n+1)}{2}$
  $\displaystyle\sum_{i=1}^n i^2 = \displaystyle\frac{n(n+1)(2n+1)}{6}$	$\displaystyle\sum_{i=0}^n r^i = \displaystyle\frac{r^{n+1} - 1}{r - 1}$

1. $\lfloor \log_2 h \rfloor$
2. $2h + 1$
3. $2^h - 1$
4. $2^h + h$
5. $h!$

The Wonder and Joy of Binary Trees

• We will spend a lot of time thinking about binary trees.
• Why????
• Question for you:
  • What is the maximum number of nodes in a binary tree of height $h$?
  • $N(h) \leq 2^h - 1$

Exercise #2

• What is the minimum height of a binary tree with $n$ nodes?
• $H(n) >= ??$

2. $\lceil \log_2 n \rceil + 1$
3. $\lfloor \log_2 n \rfloor + 1$
4. $\lfloor \frac{n}{2} \rfloor$
5. $n$
6. $2^n$

Exercise #2

• What is the minimum depth of a binary tree with $n$ nodes?
• $H(n) >= \lfloor \log_2 n \rfloor + 1$

Take Home Message

• In a linked list we store a reference to one node, all other nodes are reachable by following $O(n)$ references.

• In a binary tree we store a reference to one node, all other nodes were reachable by following $O(\log_2 n)$ references.

Traversals

Traversals

Trace the following traversal method...

  public static <E> void mystery(BinNode<E> rt) {
    Queue<BinNode<E>> queue = new LQueue<>();

    queue.enqueue(rt);

    while (queue.length() > 0) {
      BinNode<E> cur = queue.dequeue();

      visit(cur);

      if (cur.left() != null) {
        queue.enqueue(cur.left());
      }
      if (cur.right() != null) {
        queue.enqueue(cur.right());
      }
    }

  }