Trees and Recursion

import java.util.Random;

public class BinaryTree {
  private static Random random = new Random();
  private class Node {
    private Object value;
    private Node right;
    private Node left;
    Node(Object setValue) {
      value = setValue;
    }
  }
  private Node root;
  private int currentSize = 0;
  BinaryTree(Object[] values) {
    for (Object value : values) {
      add(root, value);
    }
  }
  public void add(Object value) {
    add(root, value);
  }
  private void add(Node current, Object value) {
    if (current == null) {
      root = new Node(value);
      currentSize++;
      return;
    }
    if (random.nextBoolean()) {
      if (current.right == null) {
        current.right = new Node(value);
        currentSize++;
      } else {
        add(current.right, value);
      }
    } else {
      if (current.left == null) {
        current.left = new Node(value);
        currentSize++;
      } else {
        add(current.left, value);
      }
    }
  }
  public int size() {
    return currentSize;
  }
  public String toString() {
    return toString(root);
  }
  private String toString(Node current) {
    if (current == null) {
      return "";
    }
    return "[" + current.value.toString() + "]" +
      toString(current.right) + toString(current.left);
  }
}
public class Example {
  public static void main(String[] unused) {
    BinaryTree tree = new BinaryTree(new Integer[] { 1, 2, 5, 8, 9 });
    System.out.println(tree.size());
    System.out.println(tree);
  }
}

Trees and Recursion
> Click or hit Control-Enter to run Example.main above

In computer science, a tree is a widely used data structure that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

Each parent has one or more children.

Each parent has one or more children. Each child has one parent.

We refer to the top of the tree as the root.

We refer to the top of the tree as the root. We refer to nodes without any children as leaves.

We can enumerate each level in a tree starting with the root as 0.

The depth or height of a tree is the maximum distance from root to leaf.

What kinds of data can we represent using trees?

The Java class hierarchy 1
Files on your computer
Domain names on the internet
Any data that has a hierarchical structure.

public class Pet { }
public class Dog extends Pet { }
public class Cat extends Pet { }
public class OldDog extends Dog { }

$ cd / && ls -l
System
Library
Users
$ cd Users && ls -l
challen
Shared
$ cd challen && ls -l
classes
www

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

public class Tree {
  Object value;
  Tree right;
  Tree left;
}

We are rarely interested in trees only for their structure. Usually we use them to structure data.

Every subtree of a tree is, itself, a tree.

Recursion occurs when a thing is defined in terms of itself or of its type.

public class Tree {
  Object value;
  Tree right;
  Tree left;
}

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem.

So far we’ve pursued iterative algorithms in this course. Recursion provides us with a new way to approach problems.

Iteration: repeat the same set of steps over and over again
Recursion: break a larger problem into smaller problems until they are small enough to solve easily

Let’s say that we wanted to count the number of nodes in the tree above.

We can count iteratively:

Visit every node in the tree
Increment a counter by 1 each time

We can count iteratively:

Visit every node in the tree
Increment a counter by 1 each time

We can count iteratively:

Visit every node in the tree
Increment a counter by 1 each time

We can count iteratively:

Visit every node in the tree
Increment a counter by 1 each time

We can count iteratively:

Visit every node in the tree
Increment a counter by 1 each time

We can count iteratively:

Visit every node in the tree
Increment a counter by 1 each time

We can count iteratively:

Visit every node in the tree
Increment a counter by 1 each time

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

import java.util.Random;

public class BinaryTree {
  private static Random random = new Random();
  private class Node {
    private Object value;
    private Node right;
    private Node left;
    Node(Object setValue) {
      value = setValue;
    }
  }
  private Node root;
  BinaryTree(Object[] values) {
    for (Object value : values) {
      add(root, value);
    }
  }
  public void add(Object value) {
    add(root, value);
  }
  private void add(Node current, Object value) {
    if (current == null) {
      root = new Node(value);
      return;
    }
    if (random.nextBoolean()) {
      if (current.right == null) {
        current.right = new Node(value);
      } else {
        add(current.right, value);
      }
    } else {
      if (current.left == null) {
        current.left = new Node(value);
      } else {
        add(current.left, value);
      }
    }
  }
  public int size() {
    return 0;
  }
  public String toString() {
    return toString(root);
  }
  private String toString(Node current) {
    if (current == null) {
      return "";
    }
    return "[" + current.value.toString() + "]" +
      toString(current.right) + toString(current.left);
  }
}
public class Example {
  public static void main(String[] unused) {
    BinaryTree tree = new BinaryTree(new Integer[] { 1, 2, 5, 8, 9 });
    System.out.println(tree.size());
    System.out.println(tree);
  }
}

> Click or hit Control-Enter to run Example.main above

I have office hours today from 1–2PM. Please come by!
As a reminder we have midterm preparation office hours today from 11AM–9PM. As usual, the calendar is up-to-date.
We’ve added an anonymous feedback form to the course website. Use it to give us feedback!

Trees

Trees: Parent and Child

Trees: Parent and Child

Trees: Root and Leaves

Trees: Root and Leaves

Trees: Level and Depth

Trees: Level and Depth

Trees: Level and Depth

Trees: Level and Depth

What Are Trees For?

Java Class Hierarchy

Your Computer’s Files

Domain Name Translation

Binary Trees

Subtrees As Trees

Subtrees As Trees

Subtrees As Trees

Subtrees As Trees

Subtrees As Trees

Subtrees As Trees

Subtrees As Trees

Subtrees As Trees

Subtrees As Trees

Recursion

Recursion in Computer Science

Recursion v. Iteration

Tree Node Counting

Iterative Node Counting

Iterative Node Counting

Iterative Node Counting

Iterative Node Counting

Iterative Node Counting

Iterative Node Counting

Iterative Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Announcements