3.Binary Trees§

A binary tree is made up of a finite set of nodes that is either empty or consists of a node called the root together with two binary trees, called the left and right subtrees, which are disjoint from each other and from the root.

Notation: Node, children, edge, parent, ancestor, descendant, path, depth, height, level, leaf node, internal node, subtree.

A Recursive Data Structure

A node followed by a list

Left sub-tree is a binary tree

Right sub-tree is a binary tree

Binary Tree Node Class

interface BinNode<E> { // Binary tree node ADT
  // Get and set the element value
  public E value();
  public void setValue(E v);

  // return the children
  public BinNode<E> left();
  public BinNode<E> right();

  // return TRUE if a leaf node, FALSE otherwise
  public boolean isLeaf();
}

Question

Write a recursive function named count that, given the root to a binary tree, returns a count of the number of nodes in the tree. Function count should have the following prototype:
```
int count(BinNode root)
```

Traversals

Any process for visiting the nodes in some order is called a traversal.
Any traversal that lists every node in the tree exactly once is called an enumeration of the tree’s nodes.
Preorder traversal: Visit each node before visiting its children.
Postorder traversal: Visit each node after visiting its children.
Inorder traversal: Visit the left subtree, then the node, then the right subtree.

Preorder Traversal (1)

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
}

Preorder Traversal (2)

1 / 56 Settings

<<<>>>

Preorder traversal begins.

static void preorder(BinNode 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
}

Saving...

Server Error
Resubmit

How not to write a traversal

// This is a bad idea
static <E> void preorder2(BinNode<E> rt) {
  visit(rt);
  if (rt.left() != null) { preorder2(rt.left()); }
  if (rt.right() != null) { preorder2(rt.right()); }
}

Problems:

1. This has a major bug

2. It puts the focus in the wrong place: Should focus on the current node, not the children. This version is therefore more complicated.

Recursion Examples

static <E> int count(BinNode<E> rt) {
  if (rt == null) { return 0; }  // Nothing to count
  return 1 + count(rt.left()) + count(rt.right());
}

1 / 4 Settings

<<<>>>

When you write a recursive method that traverses a binary tree, you should avoid the following common mistakes.

static int bad_count(BinNode root) {
if (root == null) { return 0; } // Nothing to count
bad_count(root.left());
1 + bad_count(root.left()) + bad_count(root.right());
}

Saving...

Server Error
Resubmit

Full and Complete Binary Trees

Full binary tree: Each node is either a leaf or internal node with exactly two non-empty children.

Complete binary tree: If the height of the tree is $d$ , then all leaves except possibly level $d$ are completely full. The bottom level has all nodes to the left side.

(a)

(b)

Full Binary Tree Theorem (1)

Theorem: The number of leaves in a non-empty full binary tree is one more than the number of internal nodes.

Proof (by Mathematical Induction):

Base case: A full binary tree with 1 internal node must have two leaf nodes.

Induction Hypothesis: Assume any full binary tree T containing $n-1$ internal nodes has $n$ leaves.

Full Binary Tree Theorem (2)

Induction Step: Given tree T with $n$ internal nodes, pick internal node $I$ with two leaf children. Remove $I$ ’s children, call resulting tree T’.

By induction hypothesis, T’ is a full binary tree with $n$ leaves.

Restore $I$ ’s two children. The number of internal nodes has now gone up by 1 to reach $n$ . The number of leaves has also gone up by 1.

Full Binary Tree Corollary

Theorem: The number of null pointers in a non-empty tree is one more than the number of nodes in the tree.

Proof: Replace all null pointers with a pointer to an empty leaf node. This is a full binary tree.

Dictionary

/** The Dictionary abstract class. */
public interface Dictionary<K, E> {

  /** Reinitialize dictionary */
  public void clear();

  /** Insert a record
      @param k The key for the record being inserted.
      @param e The record being inserted. */
  public void insert(K key, E elem);

  /** Remove and return a record.
      @param k The key of the record to be removed.
      @return A maching record. If multiple records match
      "k", remove an arbitrary one. Return null if no record
      with key "k" exists. */
  public E remove(K key);

  /** Remove and return an arbitrary record from dictionary.
      @return the record removed, or null if none exists. */
  public E removeAny();

  /** @return A record matching "k" (null if none exists).
      If multiple records match, return an arbitrary one.
      @param k The key of the record to find */
  public E find(K key);

  /** @return The number of records in the dictionary. */
  public int size();
}

.

Dictionary (2)

How can we implement a dictionary?
- We know about array-based lists and linked lists.
- They might be sorted or unsorted.
- What are the pros and cons?