What is the maximum possible height of a tree with n nodes (not necessarily a binary tree)? What is the minimum possible height? Justify your answers.

What is the maximum number of nodes on level k of a binary tree? (Consider the root of the tree to be at level 0 of the tree.)

Recall that a leaf is a tree node that has no children. In terms of n, the number of nodes in a tree (including leaves), what is the maximum number of leaves in a binary tree?

What is the maximum number of null references in a binary tree with n nodes? What is the minimum number?

Complete the following method to return the number of leaves in a binary tree, given the tree's root. A leaf is any node that has no children.

public static int countLeaves(TreeNode<E> root) {

Complete the following method so that it returns true if the parameter string word exists somewhere within the binary tree (which itself is given as a TreeNode<String> parameter referencing the tree's root). Note that the tree is not necessarily a binary search tree, so your method will have to examine all nodes of the tree to conclude that the string is not present.

public static boolean search(TreeNode<String> root, String word) {

Write the nodes of the below tree in order of their preorder traversal.

In your own words, describe the invariant for the relationship among values in a binary search tree.

Suppose we insert 5 into the below binary search tree. Assuming we use the same insertion algorithm used in the text, what will the tree look like following the insertion?

If we start with an empty binary search tree and then add values in the below order, how will the binary search tree then look?

Consider the following binary search tree.

a. Draw the binary search tree that would result from inserting 2 into the above-diagrammed tree using the discussed insertion algorithm.

b. Draw the binary search tree that would result from deleting 9 from the above-diagrammed tree using the discussed deletion algorithm.

Draw the binary search tree that would result from deleting 5 from the below tree using the discussed deletion algorithm.

Suppose we have a binary search tree as diagrammed below, and then we delete 5 using the deletion algorithm discussed in class. Diagram the resulting binary search tree.

Suppose we have the TreeNode class as discussed in class, with its getValue, getLeft, getRight, setValue, setLeft, and setRight methods. We are implementing a class encapsulating a binary search tree, as started below. Complete the getFirst method so that it returns the smallest value in the tree.

public class MyTreeSet<E> {
    private TreeNode<E> root;

    public MyTreeSet() { root = null; }

    public E getFirst() {

Write a method that, given the TreeNode representing the root of a binary search tree containing Integers, returns the second smallest element in the tree. Your method should work in O(d) time, where d is the tree's depth. (Your code need only work when the tree contains at least two elements.)

public static Integer findSecondSmallest(TreeNode<Integer> root) {

The TreeSet class in the java.util package maintains its values in order within a binary search tree. How does it tell what the order is? For example, if we have a Point class for representing two-dimensional Cartesian points, and we want to maintain a TreeSet of Points stored in increasing order based on their distance from the origin, how can we do this?

Consider the following program intended to read information about cities from the user and then display that information.

public class City {
  private String name;
  private int pop;
  
  public City(String n, int p) {
    name = n; pop = p;
  }

  public String toString() {
    return name + " (pop. " + pop + ")";
  }
}

import java.util.*;
import java.io.*;

public class Main {
  public static void main(String[] args)
      throws IOException {
    Set<City> set = new HashSet<City>();
    BufferedReader in = new BufferedReader(
        new InputStreamReader(System.in));
    while(true) {
      String line = in.readLine();
      if(line == null) break;
      StringTokenizer t = new StringTokenizer(line);
      String name = t.nextToken();
      int pop = Integer.parseInt(t.nextToken());
      set.add(new City(name, pop));
    }

    for(City c : set) {
      System.out.println(c);
    }
  }
}

Modify the program so that it displays the cities in decreasing order of population (i.e., with Little Rock first). Your modifications should not involve any sorting algorithms; instead, you should use java.util's TreeSet class (rather than its HashSet class).

Recall the TreeNode class.

public class TreeNode<E> {
    private E value;
    private TreeNode<E> left;
    private TreeNode<E> right;

    public TreeNode(E v, TreeNode<E> l, TreeNode<E> r) {
        value = v; left = l; right = r;
    }

    public E        getValue() { return value;  }
    public TreeNode getLeft()  { return left;   }
    public TreeNode getRight() { return right;  }

    public void setValue(E v)           { value = v; }
    public void setLeft(TreeNode<E> l)  { left  = l; }
    public void setRight(TreeNode<E> r) { right = r; }
}

Now suppose we are implementing a MyTreeSet class duplicating much of the functionality of java.util's TreeSet class. Complete the contains method below so that it returns true if the value of its parameter can be found in the binary search tree rooted the root instance variable.

public class MyTreeSet<E> {
    private TreeNode<E> root;

    public MyTreeSet() { root = null; }

    // (other methods, including add, omitted)

    public boolean contains(E value) {

Explain the motivation behind introducing the red-black tree data structure even though a straightforward binary search tree is much simpler.

Describe in your own words the red and black constraints for a red-black tree.

In the below tree, color the nodes that must be black so that it is a valid red-black tree.

Suppose we insert 4 into the below red-black tree. What will the tree then look like? Show your intermediate work.

Suppose we insert 7 into the below red-black tree. What will the tree then look like?

And if we then insert 8, what will the tree look like?

Suppose we have a red-black tree as diagrammed below, and then we insert 0 using the insertion algorithm discussed in class. Diagram the resulting red-black tree. Be sure to indicate which nodes are red and which are black.