More Practice with Recursion

More Practice with Recursion
> Click or hit Control-Enter to run Example.main above

I hope you all had a restful weekend.

Let’s print only leaf nodes: those that have neither a left nor a right child.

Base case: We’ve reached a tree with no left or right node. It’s also a a leaf node, so print our value.
Recursive step: Consider our right tree and left tree separately.
Combine results: Nothing to do here, just continue down the tree.

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 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 void printLeaves() {
  }
}
public class Example {
  public static void main(String[] unused) {
    BinaryTree binaryTree = new BinaryTree(new Integer[] { 1, 2, 3, 4 });
    binaryTree.printLeaves();
  }
}

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

Starting today we’ll be assigning a small amount of credit on each homework problem for writing "perfect" code.

Obviously we can’t tell whether your code is really perfect 1—meaning correct, beautiful, minimal, concise, readable. But for the purposes of automated checking we will consider your code not to be perfect if:

It contains dead or unreachable code.
It is overly complex compared to our solution.

public class YourBinaryTree extends BinaryTree {
  public int size() {
    return size(root);
  }
  private int size(Node current) {
    if (current == null) {
      return 0;
    }
    if (current != null) {
      return 1 + size(current.left) + size(current.right);
    } else {
      return 0;
    }
  }
}

The last return 0 will never be reached!

public class YourBinaryTree extends BinaryTree {
  public int size() {
    return size(root);
  }
  private int size(Node current) {
    if (current == null) {
      return 0;
    }
    if (current.left == null) {
      return 1 + size(current.right);
    } else if (current.right == null) {
      return 1 + size(current.left);
    } else {
      return 1 + size(current.right) + size(current.left);
    }
  }
}

There are 5 paths through size(Node current)
For the solution there are only 2.

Let’s determine whether a tree contains a certain value.

Base case: We’ve reached a node with no descendants. Return true if its value matches, zero otherwise.
Recursive step: Consider our right tree and left tree separately.
Combine results: Return true if either we or our right or left subtree contain the search value.

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 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 boolean search(Object value) {
  }
}
public class Example {
  public static void main(String[] unused) {
    BinaryTree binaryTree = new BinaryTree(new Integer[] { 1, 2, 3, 4 });
		System.out.println(binaryTree.search(4));
  }
}

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

public class BinarySearchTree {
  private class Node {
    private Comparable value;
    private Node right;
    private Node left;
    Node(Comparable setValue) {
      value = setValue;
    }
  }
  private Node root;
  BinarySearchTree(Comparable[] values) {
    for (Comparable value : values) {
      add(root, value);
    }
  }
  public void add(Comparable value) {
    add(root, value);
  }
  private void add(Node current, Comparable value) {
    if (current == null) {
      root = new Node(value);
      return;
    }
    if (current.value.compareTo(value) >= 0) {
      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 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 boolean search(Object value) {
  }
}
public class Example {
  public static void main(String[] unused) {
    BinarySearchTree binarySearchTree = new BinarySearchTree(new Integer[] { 1, 2, 3, 4 });
    System.out.println(binarySearchTree.search(3));
  }
}

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

Every sub(blank) of a (blank) is, itself, a (blank).

Tree
(Contiguous) List
(Contiguous) Array

MP4 is out.
We also have our usual heavy office hours today. Come by and get started on MP4!

Welcome Back!

Recursive Tree Print Leaves

What’s Our (Recursive) Algorithm?

Recursive Tree Print Leaves

Writing Perfect Code

Dead Code

High Complexity

Questions About Perfection?

Recursive Tree Search

What’s Our (Recursive) Algorithm?

Recursive Tree Search

How Could We Make This Search More Efficient?

Other Recursive Data Structures

Announcements