Terminology

Learn all these terms:

• edge
• parent
• path
• 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)\le ??$

    ${\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)\le 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.

In-Order Traversal

public class Tree {

  public void printInOrder() {
    printInOrder(root);
  }

  private void printInOrder(Node node) {

    if (node != null) {
      printInOrder(node.getLeft());
      System.out.println(node.getItem());
      printInOrder(node.getRight());
    }

  }
}

In-Order Traversal (OO Version)

public class Node {

  public void printInOrder() {
    if (left != null) {
      left.printInOrder();
    }

    System.out.println(item);

    if (right != null) {
      right.printInOrder();
    }
  }

}

Pre-Order Traversal

  private void printPreOrder(Node node) {

    if (node != null) {
      System.out.println(node.getItem());
      printPreOrder(node.getLeft());
      printPreOrder(node.getRight());
    }

  }

Post-Order Traversal

   private void printPostOrder(Node node) {

    if (node != null) {
      printPostOrder(node.getLeft());
      printPostOrder(node.getRight());
      System.out.println(node.getItem());
    }

  }

Another Traversal

Trace the following traversal method…

  public void printMysteryOrder() {
    Queue<Node> queue = new LinkedList<>();
    
    queue.offer(root);  // enqueue
    
    while (!queue.isEmpty()) {
      Node curNode = queue.poll();  // dequeue
      System.out.println(curNode.getItem());
      
      if (curNode.getLeft() != null) {
        queue.offer(curNode.getLeft());
      }
      if (curNode.getRight() != null) {
        queue.offer(curNode.getRight());
      }
      
    }
    
  }