Trees and Recursion

"Hold On When You Get Love And Let Go When You Give It" by Stars.

You are all stars! And this a (very) good time to make sure you hold on when you get love and let go when you give it.

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

Find the right spot.
Set the reference on the preceding item to point to the new item.
Set the reference on the new item to point to the former next item.

Let’s insert value 7 at index 1.

But wait, now we can’t change the preceding reference.

Let’s insert value 7 at index 1.

public class SimpleLinkedList {
  class Item {
    Object value;
    Item next;
    Item(Object setValue, Item setNext) {
      value = setValue;
      next = setNext;
    }
  }
  private Item start;
}

What we’ve been discussing is known as a singly linked list.

public class SimpleDoublyLinkedList {
  class Item {
    Object value;
    Item next;
    Item previous;
    Item(Object setValue, Item setNext) {
      value = setValue;
      next = setNext;
    }
  }
  private Item start;
  private Item end;
}

You can also have both forward and backward links. This is known an a doubly linked list.

public class SimpleDoublyLinkedList {
  class Item {
    Object value;
    Item next;
    Item previous;
    Item(Object setValue, Item setNext) {
      value = setValue;
      next = setNext;
    }
  }
  private Item start;
  private Item end;
}

public class SimpleArrayList {
  private Object[] array;
}
public class SimpleDoublyLinkedList {
  class Item {
    Object value;
    Item next;
    Item previous;
  }
  private Item start;
  private Item end;
}

ArrayList v. LinkedList also represents a time v. space tradeoff.

LinkedList is faster for certain operations…
but consumes more space to store the same amount of information.

public class SimpleArrayList {
  private Object[] array;
}
public class SimpleDoublyLinkedList {
  class Item {
    Object value;
    Item next;
    Item previous;
  }
  private Item start;
  private Item end;
}

To store n ints:

ArrayList: n values
LinkedList: 3n (1 value, 1 next, 1 previous)

Both provide the same functionality, but with different performance characteristics.

Operation ArrayList LinkedList

Operation	`ArrayList`	`LinkedList`
`add` (at front)	O(n)	O(1)
`get` and `set`	O(1)	O(n)
`insert` (anywhere)	O(n)	O(n)

add (at front)

O(n)

O(1)

get and set

O(1)

O(n)

insert (anywhere)

O(n)

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

No office hours today.
Office hours resume as scheduled tomorrow at noon.

Today’s Musical Selections

LinkedList Insertion Algorithm

Insertion Example

Insertion Example

Insertion Example

Insertion Example

Insertion Example

Insertion Example

Singly Linked Lists

Doubly Linked Lists

Doubly Linked Lists

Time v. Space

Time v. Space

ArrayList v. LinkedList

Questions About Lists?

Onward! 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

`LinkedList` Insertion Algorithm

`ArrayList` v. `LinkedList`