Practice with 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;
  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 class Example {
  public static void main(String[] unused) {
    BinaryTree tree = new BinaryTree(new Integer[] {1, 2, 5, 8, 9});
    System.out.println(tree);
  }
}

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

I have good news and good news…

Good news: you did well on Midterm 1!
Good news: we have a fantastic new MP checkpoint for you to enjoy…
Good news: we still have over a month left together.

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.

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

Recursion can be hard to wrap your mind around at first. But these three strategies will help.

Know when to stop. When you identify the smallest subproblem, you must return. Otherwise your program will not terminate. This is also called the base case.
Make the problem smaller in each step. If the problem doesn’t get smaller, you will never reach the base case. This is also called the recursive step.
Combine results from your recursive calls properly.

int factorial(int n) {
  if (n == 1) {
    return 1;
  } else {
    return n * factorial(n - 1); // I called myself!
  }
}

Base case: n == 1
Recursive step: decrement n towards 1
Combine results: multiply current n with the result of the next subproblem

int factorial(int n) {
  if (n == 1) {
    return 1;
  } else {
    return n * factorial(n - 1); // I called myself!
  }
}

You must reach the base case. Otherwise your problem will never stop, run out of memory, and crash.

How can the code above fail to reach the base case?

> Click or hit Control-Enter to run the code above

Recursive solutions can be difficult to understand.

The goal is to write clear code, not use a particular solution technique.
If an iterative solution is more clear, use that.
Sometimes a recursive solution is much more clear.
Don’t use recursion just to be cool.
Don’t use recursion because it is fewer lines of code. Who cares? Clarity is the goal, not brevity.

> Click or hit Control-Enter to run the code above

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);
      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 int rightGreaterThanLeft() {
  }
}

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

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

I got nothing. Have a great weekend!

Good News, Good News

Trees

Review: Trees: Parent and Child

Review: Trees: Parent and Child

Review: Trees: Root and Leaves

Review: Trees: Root and Leaves

Review: Trees: Level and Depth

Review: Trees: Level and Depth

Review: Trees: Level and Depth

Review: Trees: Level and Depth

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

Recursive Strategies

Recursive Factorial

Reaching Base Camp

Recursion v. Iteration

Recursive Tree Right Greater Than Left

What’s Our (Recursive) Algorithm?

Recursive Tree Right Greater Than Left

Questions About Recursion?

Announcements