Binary Trees

• A tree where each node has at most 2 children
• Each node has left and right child
• Left/right position matters (unlike in a general tree)
• Some uses for binary trees
  • Decision trees (yes/no children)
  • Huffman trees (0/1 encoding)
  • Binary search trees
  • Expression trees

Decision Trees

Decision Trees

• Basis for expert systems
• It can be used in an application where the system "learns"

Balanced Trees

Class Question 1

Consider a binary tree of height h. What is the smallest number of leaves that the tree can have?

1. 1
2. h
3. 2^{h - 1}
4. 2^h - 1

Size of a binary tree

• Smallest number of leaves is 1 in the case of degenerate binary tree
• Must have at least one leaf
• Can have at most 2^{h - 1} leaves
• Can have at most 2^h - 1 nodes

Binary Tree Implementation

public class BinaryTree
{
   private Node root;
   public BinaryTree() { root = null; } // An empty tree
   public BinaryTree(Object rootData, BinaryTree left, BinaryTree right)
   {
      root = new Node();
      root.data = rootData;
      root.left = left.root;
      root.right = right.root;
   }
   class Node
   {
      public Object data;
      public Node left;
      public Node right;
   }
   . . .
}

Class Question 2

What are the leaves of the tree

new BinaryTree("Fred", 
   new BinaryTree("Barney", null, null),
   new BinaryTree("Dino", 
      new BinaryTree("Wilma", null, null),
      null));

1. Fred
2. Wilma
3. Barney and Wilma
4. Something else

Recursive Computation of height

height(tree) = 1 + max(height(left), height(right))

Class Question 3

What is wrong with this implementation of the height method of a BinaryTree class?

public class BinaryTree
{
   . . .
   public int height() { return height(root); }
  
   class Node
   {
      private int height(Node n)
      {
         if (n == null) { return 0; }
         else 
         { 
            return 1 + Math.max(height(n.left), height(n.right)); 
         }
      }
      ...
   }
   
   . . .
}

1. The public height method should have been static
2. The private height method should have been static
3. The returned values are off by one from the actual heights
4. There is nothing wrong--the method works correctly

Class Question 4

What is wrong with this implementation of the height method of a BinaryTree class?

public class BinaryTree
{
   . . .
   public int height() { return height(root); }
  
   private static int height(Node n)
   {
      if (n == null) { return 0; }
      else { return Math.max(height(n.left), height(n.right)); }
   }
   . . .
}

1. The public height method should have been static
2. The method returns the wrong value for every tree
3. The method returns the wrong value for every non-empty tree
4. There is nothing wrong--the method works correctly

Java heading

More about Java.