**Section 5.1:**
[1]
[2]
[3]
[4]
[5]
[6]
[7]
**Section 5.2:**
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
**Section 5.3:**
[1]
[2]
[3]
[4]
[5]
[6]

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.

The height could be as much as `n`, if each node has
exactly one child, so that we end up with what amounts to a singly
linked list. Assuming `n` > 1, the minimum
height is 2, with the root at the first level and all the other
`n` − 1 nodes being children of that. If
`n` > 1, the height cannot be less than 2,
because only one node can be on the first level; and neither can the
height be more than `n`, because each level must have at
least one node.

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.)

2^{k}

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?

There will be `n` / 2 leaves if `n` is
even, and (`n` + 1) / 2 leaves if
`n` is odd. This can be abbrevated mathematically
to ⌊(`n` + 1) / 2⌋
using the **floor function** signified by
⌊…⌋ which means to round down.

It can also be abbreviated to ⌈`n` / 2⌉
using the **ceiling function**, which means to round
up.

What is the maximum number of `null`

references
in a binary tree with `n` nodes? What is the minimum
number?

There are exactly `n` + 1 `null`

references in an `n`-node binary tree, so the minimum and
maximum are both `n` + 1. The argument for why this
is so proceeds as follows: Suppose we begin with an empty tree, where
`n` = 0; this has of course 1 `null`

reference. As we insert each node, we replace a `null`

reference to refer to that node instead, but then the new node
has two new `null`

references, for a net gain of one
`null`

reference per inserted node.

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) {

if(root.getLeft() == null && root.getRight() == null) { return 1; } else { int n = 0; if(root.getLeft() != null) n += countLeaves(root.getLeft()); if(root.getRight() != null) n += countLeaves(root.getRight()); return n; } }

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) {

if(root == null) return false; return root.getValue().equals(word) || search(root.getLeft(), word) || search(root.getRight(), word)); }

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

*a b d h i e j c f k g l m*

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

For every node, its value is greater than all the values in its left subtree, and its value is less than (or equal to) all the values in its right subtree.

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.

**a.**

**b.** Either of the following would be acceptable answers.

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

Either of the following would be acceptable answers.

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.

[An alternative solution makes 6 be the root, with the left child of 8 now being the 7.]

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() {

if(root == null) { throw new NoSuchElementException(); } else { TreeNode<E> n = root; while(n.getLeft() != null) { n = n.getLeft(); } return n.getValue(); } } }

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) {

// Proceed down the left spine of the tree to reach the // smallest. The prev variable is always n's parent. TreeNode<Integer> prev = null; TreeNode<Integer> n = root; while(n.getLeft() != null) { prev = n; n = n.getLeft(); } if(n.getRight() != null) { // the second smallest will be the smallest in the // smallest's right subtree, if it exists n = n.getRight(); while(n.getLeft() != null) n = n.getLeft(); return n.getValue(); } else { // if the smallest has no right subtree, the second // smallest is the smallest's parent return prev.getValue(); } }

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?

It uses the objects' `compareTo`

method to determine the
ordering. In the Point example, we would want to define Point as
implementing the Comparable interface, including a
`compareTo`

method such as the following.

public int compareTo(Point that) { double thisDist = this.distanceToOrigin(); double thatDist = that.distanceToOrigin(); if(thisDist > thatDist) return 1; else if(thisDist < thatDist) return -1; else return 0; }

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).

First, we must modify the City class to implement Comparable by modifying the first line to:

public class City implements Comparable<City> {

and adding the `compareTo`

method to compare
populations.

public int compareTo(Object o) { return ((City) o).pop - this.pop; }

Then, we simply modify `main`

to use a TreeSet rather
than a HashSet.

Set<City> set = new TreeSet<City>();

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) {

TreeNode<E> n = root; while(n != null) { int comp = o.compareTo(n.getValue()); if(comp < 0) n = n.getLeft(); else if(comp > 0) n = n.getRight(); else return true; } return false; }

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

In the worst case, a binary search tree has a height of `n`.
As a result, if we use a simple BST to implement the Set ADT, the
`add`

and `contains`

methods would take
`O`(`n`)
time. The red-black tree ensures that the tree's height is
`O`(log `n`),
and thus the `add`

and `contains`

methods can
guarantee `O`(log `n`) speed.

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

**The red constraint:**All red nodes can have only black children.**The black constraint:**For every path from the root to a`null`

reference, the number of black nodes on the path must be the same.

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

[This is the only correct solution.]

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?

After inserting 7, we have:

After inserting 8 to the previous tree, we have:

[The intermediate work shown above was not requested in the problem.]

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.