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 find the number of nodes in our tree where the value of the right child is greater than or equal to value of the left child.

Base case: We’ve reached a tree with one node. It does not have a right child or left child, so we can return 0.
Recursive step: Consider our right tree and left tree separately.
Combine results: Determine whether our right child is greater than our left child. If so, add 1 to the sum of results from our left and right child.

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);
    } else if (current.right == null) {
      current.right = new Node(value);
    } else if (current.left == null) {
      current.left = new Node(value);
    } else if (random.nextBoolean()) {
      add(current.right, 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 int rightGreaterThanLeft() {
  }
}

public class Example {
  public static void main(String[] unused) {
    BinaryTree binaryTree = new BinaryTree(new Integer[] { 1, 2, 3, 4 });
    System.out.println(binaryTree.rightGreaterThanLeft());
  }
}

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

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);
    } else if (current.right == null) {
      current.right = new Node(value);
    } else if (current.left == null) {
      current.left = new Node(value);
    } else if (random.nextBoolean()) {
      add(current.right, 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

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);
    } else if (current.right == null) {
      current.right = new Node(value);
    } else if (current.left == null) {
      current.left = new Node(value);
    } else if (random.nextBoolean()) {
      add(current.right, 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

public class Item {
  public int value;
  public Item next;
  Item(int setValue, Item setNext) {
    value = setValue;
    next = setNext;
  }
}

public class Item {
  public int value;
  public Item next;
  Item(int setValue, Item setNext) {
    value = setValue;
    next = setNext;
  }
}

public class Item {
  public int value;
  public Item next;
  Item(int setValue, Item setNext) {
    value = setValue;
    next = setNext;
  }
}

public class Item {
  public int value;
  public Item next;
  Item(int setValue, Item setNext) {
    value = setValue;
    next = setNext;
  }
}

public class Item {
  public int value;
  public Item next;
  Item(int setValue, Item setNext) {
    value = setValue;
    next = setNext;
  }
}

Just like with trees, we need a way to both make the problem smaller and identify the smallest subproblem.

How do we make the problem smaller? Break the list into the current item and the rest of the list.
What’s the smallest subproblem? A list with a single element.

Given a linked list, reverse the elements in the list.

Base case: We’ve reached a list with one element. No need to do anything, since it’s the same reversed.
Recursive step: Consider the current element and the rest of the list separately.
Combine results: Add the current element as the last element of the reversal of the rest of the list.

public class Item {
  public int value;
  public Item next;
  Item(int setValue, Item setNext) {
    value = setValue;
    next = setNext;
  }
}
public class LinkedList {
  private Item start;
  public LinkedList(Integer[] array) {
    for (int i = 0; i < array.length; i++) {
      this.addToEnd(array[i]);
    }
  }
  public void addToEnd(int value) {
    Item item = new Item(value, null);
    if (start == null) {
      start = item;
      return;
    }
    Item current;
    for (current = start; current.next != null; current = current.next);
    current.next = item;
  }
  public String toString() {
    String string = "";
    Item current = start;
    while (current != null) {
      string += current.value + " ";
      current = current.next;
    }
    return string.trim();
  }
  public void reverse() {
    if (start != null) {
      start = start.reverse();
    }
  }
}
public class Example {
  public static void main(String[] unused) {
    LinkedList myList = new LinkedList(new Integer[] { 1, 2, 3 });
    System.out.println(myList);
  }
}

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

// Set ourselves as the end of the list
current.next.next = current;

// Mark that the item after us is null
current.next = null;

At this point we’ve reversed the end of the list.
But Item6 still has a reference to what was its next element, but is now the end of the rest of the list.
So we can use that to set it as the last item.

// Set ourselves as the end of the list
current.next.next = this;

// Mark that the item after us is null
current.next = null;

At this point we’ve reversed the end of the list.
But Item6 still has a reference to what was its next element, but is now the end of the rest of the list.
So we can use that to set it as the last item.

// Set ourselves as the end of the list
current.next.next = this;

// Mark that the item after us is null
current.next = null;

At this point we’ve reversed the end of the list.
But Item6 still has a reference to what was its next element, but is now the end of the rest of the list.
So we can use that to set it as the last item.

MP5 is out. It’s our first (and only) completely new MP this semester.

A huge shout out to Ben Nordick and Bailey Tincher: the two course developers who led the development of this fantastic MP.
MP5 is new, meaning the course assistants have not yet completed it. As always, the course staff will be working as hard as possible to support MP5.
MP5 is not intended to be easy, but will be extremely worthwhile to complete. It introduces you to a new and extremely powerful data structure: graphs.
MP5 is not about chemistry. It’s about computer science. The core programming tasks are common graph algorithms.

MP5 is out! Get started.
I have office hours today from 10AM–12PM. Please come by!
Note that we will have class on the Friday before Thanksgiving but not on the Wednesday before Thanksgiving. 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!

Welcome Back!

Recursive Tree Right Greater Than Left

What’s Our (Recursive) Algorithm?

Recursive Tree Right Greater Than Left

Recursive Tree Print Leaves

What’s Our (Recursive) Algorithm?

Recursive Tree Print Leaves

Recursive Tree Search

What’s Our (Recursive) Algorithm?

Recursive Tree Search

How Could We Make This Search More Efficient?

Other Recursive Data Structures

List Recursion

List Recursion

List Recursion

List Recursion

List Recursion

List Recursion

Linked List Reversal

What’s Our (Recursive) Algorithm?

Linked List Reversal

This Is Tricky

Recursive List Reversal

Recursive List Reversal

Recursive List Reversal

MP5

Announcements