Terminology

Learn all these terms:

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

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{1 - r^{n+1}}{1 - r}\)

1. \(\lfloor \log_2 h \rfloor\)
2. \(2h + 1\)
3. \(2^{h+1} - 1\)
4. \((2h^3 + 3n^2 + n) / 6\)
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} - 1\)

Exercise #2

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

1. \(\lceil \log_2 n \rceil\)
2. \(\lfloor \log_2 n \rfloor\)
3. \(\lfloor \frac{n}{2} \rfloor\)
4. \(n\)
5. \(2^n\)

Exercise #2

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

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 are reachable by following \(O(\log_2 n)\) references.

Pre-Order Traversal

static <E> void preorder(BinNode<E> rt) {
  if (rt == null) { return; } // Empty subtree - do nothing
  visit(rt);              // Process root node
  preorder(rt.left());    // Process all nodes in left
  preorder(rt.right());   // Process all nodes in right
}

In-Order Traversal

static <E> void inorder(BinNode<E> rt) {
  if (rt == null) { return; } // Empty subtree - do nothing
  inorder(rt.left());     // Process all nodes in left
  visit(rt);              // Process root node
  inorder(rt.right());    // Process all nodes in right
}

Post-Order Traversal

static <E> void postorder(BinNode<E> rt) {
  if (rt == null) { return; } // Empty subtree - do nothing
  postorder(rt.left());    // Process all nodes in left
  postorder(rt.right());   // Process all nodes in right
  visit(rt);               // Process root node
}

Another Traversal

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());
      }
    }

  }