4.3 LINKED STRUCTURES

This section under major construction.

Linked structures. When writing computer programs, we are often faced with the problem of organizing huge quantities of related data. An array is a quintessential data structure for storing information that provides direct access to an element given its index. In this section we will consider more flexible user-defined mechanisms for associating related information that enables us to efficiently access elements and rearrange their order. In Sections XX, YY, and ZZ we will use linked structures to build useful higher level abstractions called stacks, queues, hash tables, binary search trees, and graphs. In this section we will concentrate on understanding their properties and how to implement them in Java. Knowing when and how to use linked structures is one of the defining skills that separates novice and advanced programmers.

Linked lists. When we write Java programs, we often want to store collections of objects. An array stores a sequence of objects, and we access each object by its index. One drawback of arrays is that we have to fix the size of the array when we create it with new. In many applications we need to be able to insert and remove elements from the collection. Linked lists provide a convenient mechanism for storing and accessing objects in a collection where the number of objects is not known ahead of time. Linked list also provide a stepping stone to more advanced linked structures like trees.

A linked list is defined recursively. It is a sequence of nodes, where each each node contains some data plus a link to another node. In a linear linked list, all of the links are distinct and the last node has a null link. A circular linked list is similar, but the last node links back to the first node. A linked list node knows only about itself (some piece of data) and what is the next node in the list. It is like a freight train, that is coupled to the next freight train in the sequence. It is convenient to draw a linked list using box and pointer notation. The shaded boxes store data and the white boxes store references to other boxes. We direct an array from the reference to what it points to. We use cross-hatching to illustrate the reference to null.

Null-terminated and circular linked lists

Linked lists in Java. Defining a linked list data type in Java is easy. For concreteness, we will describe how to create a linked list of strings. We implement linked lists nodes as objects of type OneNode: each node contains a reference to a string plus a reference to a node. We use references to nodes to implement links.

public class OneNode {
    String value;
    OneNode next;
}

Program OneNode.java illustrates how to create a linked list of the three strings "Carol", "Bob", and "Alice." Note how we use null to terminate the list.

OneNode a = new OneNode();
a.value = "Alice";
a.next  = null;
OneNode b = new OneNode();
b.value = "Bob";
b.next  = a;
OneNode c = new OneNode();
c.value = "Carol";
c.next  = b;

The following code fragment builds up a linked list by reading in strings from standard input, creating a new OneNode that contains a reference to the string, and inserting the node at the front of the list. This yields a linked list with the strings in the reverse order in which they were inserted.

OneNode first = null;
while(!StdIn.isEmpty()) {
    String s = StdIn.readString();
    OneNode x = new OneNode();
    x.value = s;
    x.next  = first;
    first = x;
}

List traversal.

One of the most common operations we perform on arrays and lists is to iterate over each element. The following idiomatic code prints out each of the items in a null-termianted linked list. We initialize a loop index variable x to reference the first node of the linked list. As long as x is not null, we print out it's value field. Then we update x to reference the next node on the linked list and repeat the process.

for (OneNode x = first; x != null; x = x.next)
    System.out.println(x.value);

See Exercise XYZ for traversing a circular linked list.

Arrays vs. linked lists. The main advantage of linked lists over arrays is flexibility. With arrays, we must specify the fixed size of the array when we declare it. With linked lists, we can gracefully add new nodes (until our system runs out of memory). A prime advantage of arrays over linked lists is that arrays provides random access to the elements: it is possible to directly access any element given its index. In contrast, linked lists provide only serial access: from a given node we can only directly access the next node. It is easy to efficiently simulate serial access with an array, but simulating random access with a linked list (See exercise XYZ) is inefficient. We can best understand the performance tradeoffs between arrays and linked lists by examing how they are represented in computer memory. When you create an array of one million elements, the system reserves enough space for exactly one million elements. This space is located consecutively in memory so that the system can access the ith element, given the memory address of the 0th element and the offset i. In contrast, when you create a linked list, the system allocated only one node at a time. Each node stores the memory address of the next node in the list. As a consequence, there is no need to store the linked list nodes consecutively in memory (or even specify the number of elements that the linked list will store ahead of time).

Elementary list processing. One of the prime advantages of a linked list is its flexibility. As a warmup, we first describe how to delete and insert a node into the middle of a linked list. Suppose that x is a linked list node and we want to delete the node immediately following x. Let y be a reference to the next node and z the one after that. We accomplish the deletion by changing the next field of x to be z. Assuming there are no outstanding references to the deleted node, the garbage collector will reclaim the memory once y changes values or goes out of scope.

OneNode y = x.next;
OneNode z = y.next;
x.next = z;

Suppose that x is a linked list node, and that we want to insert the linked list node t so that it immediately follows x. We achieve this by changing the next fields of both x and t.

OneNode y = x.next;
t.next = y;
x.next = t;

Functions on linked lists. It is easy to write functions that manipulate linked lists. As a first example, let's write a function count that takes as input a reference to the first node of a linked list and returns the total number of elements in the list, or 0 if the list is empty.

public static int count(OneNode list) {
   int n = 0;
   for (OneNode x = list; x != null; x = x.next)
      n++;
   return n;
}

There is an inherent ambiguity as to whether we view an object of type OneNode as a reference to a single node of a linked list or as a referene to linked list beginning at that node. Both interpretations are correct and can be used interchangeably. To emphasise which interpretation we are using, we name the variable list or first accordingly. We declare count as a classwide (static) method instead of an instance method because we want to be able to deal with empty linked lists. It is legal to pass null to a static method, but it is illegal to invoke an object method with null.

Since linked lists are defined recursively, it is straightforward to traverse a list using recursion. The following recursive function counts the number of elements in a linked list. The length of an empty linked list is zero (the base case), and the length of a non-empty linked list is one more than the length of the linked list starting at the second node.

public static int count(OneNode list) {
   if (list == null) return 0;
   OneNode rest = list.next;
   else return 1 + count(rest);
}

The recursive version is less efficient than the iterative version because it uses stack space proportional to the number of elements in the linked list (although an optimizing compiler might identify the tail recursion and convert it into the iterative version). Our main goal for showing the recursive version is that it is extremely useful when dealing with more complicated linked structures, including binary trees.

As a more sophisticated example, we consider the task of reversing the elements in a linked list. To accomplish this, we maintain references to three consecutive nodes in the linked list, reverse, first, and second. At each iteration we extract the node first from the original linked list and insert it at the beginning of the reversed list. We maintain the invariant that first is the first node of what's left of the original list, second is the second node of what's left of the original list, and reverse is the first node of the resulting reversed list.

public static OneNode reverse(OneNode list) {
   OneNode first   = list;
   OneNode reverse = null;
   while (first != null) {
      OneNode second = first.next;
      first.next  = reverse;
      reverse     = first;
      first       = second;
   }
   return reverse;
}

When writing code involving linked lists, we must always be careful to properly handle the exceptional cases (when the linked list is empty, when the list has only one or two nodes) and the boundary cases (dealing with the first or last items). This is usually the trickiest part, as opposed to handling the normal cases. We encourage you to verify that our reverse function works in all of these cases, even if the list is empty.

Trees. Trees are a mathematical abstraction that play a central role in the efficient organization of information. Like arrays and linked lists, a tree is a data type that stores a collection of data. Arrays and linked lists capture the ordered structure of elements in a collection. Trees are capable of capturing hierarchical structure. We are accustomed to many tree structures in everyday life including family trees, NCAA basketball tournament tree, the organization chart of a large company, and parse trees in grade school grammar. Trees also arise in numerous computer science applications including function call trees, parse trees, binary search trees, and file systems. However, many of their most prolific applications are rooted in science and engineering, including phylogenetic trees in computational biology, 2-d and k-d trees in computer graphics, minimax game trees in economics, and quad trees in molecular dynamics simulations.

Binary trees. Binary trees play an important role in computer programming because they strike a nice balance between flexibility and ease of implementation. A binary tree is defined recursively. It is a collection of nodes, where each each node contains some data plus two links to other nodes, called the left and right subtrees. Either or both links may be null. We assume all of the subtrees are disjoint. A binary tree node knows only about itself (some piece of data) and its left and right subtrees.

Binary trees in Java. Defining a binary tree in Java is almost exactly the same as a linked list, except that we allow for two links instead of one. For concreteness, we will describe how to create a linked list of strings. We implement a binary tree node as an object of type TwoNode: each node contains a reference to a string plus two references to other tree nodes.

public class TwoNode {
    private String value;
    private TwoNode left;
    private TwoNode right;
}

Program TwoNode.java illustrates how to create a binary tree of the five strings.

TwoNode a = new TwoNode();
a.value   = "10";
a.left    = null;
a.right   = null;

TwoNode b = new TwoNode();
b.value   = "12";
b.left    = null;
b.right   = null;

TwoNode c = new TwoNode();
c.value   = "*";
c.left    = a;
c.right   = b;

TwoNode d = new TwoNode();
d.value   = "7";
d.left    = null;
d.right   = null;

TwoNode e = new TwoNode();
e.value   = "+";
e.left    = c;
e.right   = d;

Functions on trees.

The number of elements in an empty binary tree is 0 (base case), and the number of elements in a non-empty binary tree is equal to one plus the number of elements in the left subtree plus the number of elements in the right subtree. We can quickly translate this into Java code. The following returns the number of nodes in the binary tree rooted at x.

public static int count(TwoNode x) {
   if (x == null) return 0;
   return 1 + count(x.left) + count(x.right);
}

Tree traversal.

W consider algorithms for the most basic tree-processing function: tree traversal: Given a (reference to) a tree, we want to process every node in the tree systematically. In a linked list, we move from one node to the next by following the single link; for trees, however, we have decisions to make, because there may be multiple links to follow. For linked lists, we had two basic options: process the node and then follow the link (in which case we would visit the nodes in order), or follow the link and then process the node (in which case we would visit the nodes in reverse order). For binary trees, we have two links, and we therefore have three basic orders in which we might visit the nodes:

Preorder: visit the node, then visit the left and right subtrees.
Inorder: visit the left subtree, then visit the node, then visit the right subtree.
Preorder: visit the left and right subtrees, then visit the node.

The sequences in the figure below indicate the order in which we visit nodes for a preorder(left), inorder (center), and postorder (right) tree traveral.

Preorder, inorder, and postorder traversal of a tree

Using recursion, it is easy to implement a preorder traveral as shown below.

public static void preorder(TwoNode x) {
   if (x == null) return;
   System.out.println(x.name);
   preorder(x.left);
   preorder(x.right);
}

To implement traversals in the other orders, we permute the calls in in the appropriate manner.

Parse trees. Give parse tree of English sentence. Similar ideas are extremely useful in deciphering arithmetic expressions. The program ParseTree.java reads in a preorder expression from standard input, explicitly builds a parse tree, and evaluates it. For example the prefix expression

* + + 4 5 * 6 7 8

corresponds so the infix expression (((4+5)+(6*7))*8) and is represented by the parse tree below.

Remark about s + " " + left + " " + right line and how Java knows to use concatenation.

Circuits. Create an abstract class Gate.java, and subclasses And.java, Or.java and Not.java to implement logic gates. Combine them to make Majority.java and OddParity.java. Caveat: exponential time to simulate if circuit components overlap.

Ancestor trees. Sometimes we want to create a binary tree where we can walk up the tree, in addition to walking down it. For example, in an ancestor tree, we might ask for the least common ancestor of two leaf nodes. Also useful in hierarchical clustering. In such situations we can define a tree node to have three links: one to the left child, one to the right child, and one to its parent.

public class ThreeNode {
    private String value;
    private ThreeNode left, right;
    private ThreeNode parent;
}

Program ThreeNode.java illustrates this procedure. It also includes a method to compute the least common ancestor, given references to two nodes.

Perspective on linked structures. Not all singly linked structures are linked lists (e.g., circular linked lists). Given a link to a collection of objects of type OneNode, each with a link to a OneNode, what can we say about its structural properties? Any path must end in a cycle or null, but paths could be shared. Parent-link trees. If we restrict each node to one incoming link, then it must be a linked list. Not all doubly-linked structures are doubly linked lists (e.g., binary tree). Given a link to a collection of objects of type TwoNode, each with two links to two TwoNodes, what can we say about its structural properties? If we restrict each node to have at most one incoming link, then it must be a binary tree. Branching program = exactly one source, two links per node, but no directed cycles.

Lessons

Use arrays or linked list to capture ordered structure of elements. Use binary trees to capture hierarchical structure.
Use arrays if you need random access to a collection of elements.
Choose between arrays and linked lists after considering space-time tradeoffs.

Q + A

Q. Is iterating over a linked list more efficient with a loop or recursion?

A. An optimizing compiler will likely translate a tail-recursive function into the equivalent loop, so there may be no observable performance overhead of using recursion.

Exercises

Suppose x is a linked list node. What does the following code fragment do?
x.next = x.next.next;
Suppose that x is a linked list node. What does the following code fragment do?
t.next = x.next; x.next = t;
Answer: inserts node t immediately after x.
Why does the following code fragment not do the same thing as in the previous question?
x.next = t; t.next = x.next;
Answer: when it comes time to update t.next, x.next is no longer the original node following x, but is instead t itself!
Draw using box-and-link notation the linked list that results from the following code fragment.
String s = "abracadabra"; OneNode first; for (int i = 0; i
Suppose that first is a reference to some OneNode on a circular linked list. Write a code fragment to iterate over the circular linked list and print out the string associated with each node. Solution: it's cleanest with a do-while loop.
OneNode x = first; do { System.out.println(x.value); x = x.next; } while (x != first)
Add a method count to Josephus that takes as input a TwoNode and returns the number of elements in the circular linked list.
Write an iterative method max that takes a null-terminated linked list as input, and returns the value of the maximum key in the linked list. Assume all keys are positive integers, and return -1 if the list is empty.
Repeat the previous exercise with a circular linked list.
Suppose that you add the following toString method to OneNode. If the linked list beginning at node x is "3", "1", "4", "1", "5", "9", what does System.out.println(x) print?
public String toString() { return value + " " + next; }
Given a linked list with three integer elements, write a code fragment to rearrange list so that the elements are in increasing order.
Write an iterative method delete that takes an integer parameter k and deletes the kth element (assuming it exists).
Write an iterative method delete that takes an integer parameter k and inserts an item so that it becomes the kth element (assuming the list had at least k-1 elements to begin with).
Write an iterative method cut that divides the list into two (roughly) equal halves and puts the second half at the front of the first half.
Write an iterative method dedup that removes any duplicates from a sorted list of items.
Write an iterative method last that takes an integer argument and returns the last index of a Node containing that integer, or -1 if no such integer exists.
Write an iterative method penultimate returns the second to last element in the lined list, or null if the linked list has fewer than two elements.
Write a recursive method to print the elements in reverse order. Do not modify any of the links.
Write a recursive method to reverse the elements of a linked list. It should take as input a reference to the first linked list node and return a reference to the first node of the reversed list. Hint: if the linked list has N elements, recursively reverse the last N-1 elements, then carefully append the first element to the end.
public OneNode reverse(OneNode first) { OneNode second = first.next; OneNode rest = reverse(second); second.next = first; first.next = null; return rest; }
Suppose we add the following constructor for OneNode.
public OneNode(String value, OneNode next) { this.value = value; this.next = next; } first = new OneNode("hello", first);
Why do the following two statements do?
OneNode first = null; first = new OneNode("hello", first);
Answer: it creates a null-terminated linked list of one node. Since first is null when the constructor is called, the result is equivalent to calling OneNode("hello", null). Thus, it does not create a circular linked list of one node as you might expect at first glance.
Write a program to build a null-terminated linked list containing the integers 1, 2, to N in order.
Write a program to build a circular linked list containing the integers 1, 2, to N in the order 1, N, N-1, ..., 2 by repeatedly adding each successive integer after the first node in the linked list.

Suppose that we pass the first OneNode of a null-terminated linked to mystery. Which OneNode is returned?

static Node(Node head) {
   Node x = head;
   Node xx = head;
   while(xx != null && xx.next != null) {
       x = x.next;
       xx = xx.next;
       xx = xx.next;
   }
   return x;
}

Give the preorder, inorder, postorder, and level-order traversals of the following binary trees.
Give the inorder and postorder traversal for the tree whose preorder traversal is
A B C - - D - - E - F -
The letters correspond to labeled internal nodes; the minus signs to external nodes.
Draw a binary tree of at least 5 nodes whose inorder traversal equals its preorder traversal.
How many tree shapes have the same preorder traversal as its postorder traversal? Answer: two - a tree with zero or one nodes.
Give a binary tree with integer values between 0 and 1,000,000 in the nodes, write a recursive function to compute the
1. number of the elements
2. sum of the elements
3. number of leaf nodes
4. maximum element (return -1 if the tree is empty)
5. parity of the tree (1 if sum of elements is odd, 0 otherwise)
Give a binary tree with String values, write a method to print out all strings that are lexicographically less than a given value s.
The height of a tree is the maximum number of nodes on a path from the root to a leaf node. Write a method that returns the height of a binary tree.
Suppose that root is the root node of the following two-linked structure (not a binary tree). What is count(root)?
Answer: not what you expect.
A complete binary tree is a binary tree in which each level is completely filled. Write a method isComplete that takes a binary tree and returns true if it is complete, and false otherwise. Hint: call the methods count and depth.
The cost of a path in a tree is sum of the keys of the nodes participating in that path. Write a method that returns the cost of the most expensive path from the root to a leaf node.
Write a recursive method mirror that takes a binary tree and reverse the role of left and right. For example, it would replace the first tree with the second:
A A / \ / \ B C C B / \ \ \ / \ D E F F E D
A tree is min heap-ordered if the value stored in each child is greater than or equal to the value stored in its parent. Write a method isHeapOrdered that takes a binary tree and returns true if the tree is heap ordered, and false otherwise.
Write a method equals that takes two binary trees and returns true if they are identical (same values and tree structure) and false otherwise. Hint: check that the roots of the two trees contain the same value; then recursively check the each of the two corresponding pairs of subtrees are equal.
A binary tree is said to be balanced if both of its subtrees are balanced and the height of its left subtree differs from the height of its right subtree by at most 1. Write a method to determine whether a given binary tree is balanced.

What value does mystery return when called with each of the binary trees in question 2?

int mystery(Node x) {
    if (x == null) return 0;
    else return Math.max(mystery(x.left), mystery(x.right));
}

Consider the parse tree whose preorder traversal is
* * + 1 2 + * 3 4 5 6
What is the value of the parse tree (or equivalently of the above traversal interpreted as a prefix expression)?
What's wrong with the following program?
public class Tree { int value = 0; Tree left = new Tree(); Tree right = new Tree(); public static void main(String [] args) { Tree t = new Tree(); } }
It compiles, but produces a StackOverFlowError because the (no-argument) constructor is called recursively, and there is no base case.

Creative Exercises

Prefix trees. See data compression assignment.
Circular linked lists. A circular linked list is similar to a linked list in that each node contains data (e.g., a string) and a reference to the next element in the list. However, the last element in the list points back to the first node. This models situations where the elements are ordered, but there is no "first" element, e.g., knights sitting at a round table. Imagine that N knights have decided to elect a leader by sitting at a round table and eliminating every Mth person around the circle. To simulate this process, we build a circular linked list of the N knights, 1-2-3-4-5-6-7-8-9-1. Then we proceed to eliminate every 5th person. After the first round, 5 is eliminated and the linked lists contains 1-2-3-4-6-7-8-9-1. Then 1 is eliminated, and so on. Write a program Josephus.java to model this process.
Polynomials. A univariate polynomial of degree n is a function of the form where a_n is nonzero.

For example, 17x³ + 5x + 1 or x^1000000 - 1. Implement a polynomial using a real array a of size N+1 where a[i] stores the coefficient a_i.
Sparse polynomial. Implement a polynomial ADT that stores a linked list of only those coefficients that are nonzero, say with the following subclass
public class Term { private double coef; private int exp; private Term next; }
Polynomial tradeoff. The following questions compare the array and linked list implementations of a polynomial described above. Answer in terms of running time and memory consumption. Which implementation would you prefer if the polynomial is large, but dense? If tte polynomial is huge and very sparse? If the polynomial is small?
Visualization of a binary tree. Add a method draw to ParseTree.java so that it plots the resulting parse tree. Name your program DrawableParseTree.java.
Random element of a linked list. Given a linked list, return an element of the list chosen uniformly at random. You may only make one pass through the list. Hint: traverse the list and maintain the "champion." When considering the ith element, make it the champion with probability 1/i.
Animated Josephus. Write a program to animate the Josephus elimination. Draw the N people in a circle and label each one with an integer from 1 to N. Connect them with lines, and when a person is eliminated, remove them from the circle.
Farey sequence. The Farey sequence of order N is the increasing sequence of all rational numbers (in lowest common form) between 0 and 1 whose numerator and denominator are integers between 0 and 1.
0: 0/1 1/1 1: 0/1 1/2 1/1 2: 0/1 1/3 1/2 2/3 1/1 3: 0/1 1/4 1/3 1/2 2/3 3/4 1/1 4: 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
Write a program Farey.java that takes a command line parameter N and prints the Farey sequence of order N. To generate the Farey sequence of order N, start with the list { 0/1, 1/1 } and make N-1 passes. That is, for each pair of neighboring rational numbers a/b and c/d, insert (a+c)/(b+d) assuming neither a+c or b+d is too big.
Insertion sort on linked lists.
Maze. Redo the maze generation and maze solver using OOP principles. Create a class Cell.java that represents a grid cell. It should know its four neighboring cells and the status of its four adjoining walls. It should also be able to draw itself using turtle graphics. Write a program Maze.java that takes a command line argument N and generates an N-by-N perfect maze and solves it.
Necklace. Given a necklace and black and white beads, determine the maximum number of consecutive beads of any one color. Assume the necklace is represented as a circular linked list, and the color is represented as false (white) or true (black).
Necklace with wildcards. Repeat the previous exercise, but assume there are red beads (2) as well. Find the maximum number of consecutive beads, but count the red beads as blanks which match either white or black.
Jotto. (Bob Vanderbei) Jotto is a word game where the first player chooses a secret 5 letter word. The second player tries to guess the secret word. After each guess, the first player states the number of letters (jots) that the guessed word has in common with the secret word.
1. Write a computer program for the first player. Choose a secret word at random from a list of 5 letters words that you read in from a file. Then, repeatedly prompt the user for 5 letter words. Calculate the number of jots for each guess and print it to the screen. End the game when the user guesses the correct word.
2. Write a computer program for the second player. Read in a list of 5 letters words from a file and store them in a linked list. Select a random word from the list and use it as your guess. Prompt the user for the number of jots with your random word, and delete all remaining words on the linked list that have a different number of jots. Repeat this process until there is only one word remaining (or all of the remaining words are anagrams) or the list is empty (the user cheated).
Floyd's cycle algorithm. Given a reference to the beginning of a linked list data structure, determine whether the "list" is a linear list or whether it is a path that leads to a cycle.
Solution: maintain two references x and xx. Set x = x.next and xx = xx.next.next. Repeat until xx or xx.next is null (a linear linked list) or until x == xx (a cycle).
Perfect shuffling. A perfect shuffle of a deck of cards consists of cutting the deck into two equal piles, and then interleaving the cards from each pile. A perfect in-shuffle of the cards A B C D E F G H results in E A F B G C H D whereas a perfect out-shuffle results in A E B F C G D H. Write a program that takes a command line argument N and performs N perfect out-shuffles. Note: perfect shuffling arises in a number of parallel algorithms for signal processing applications, including the Fast Fourier Transform.
Perfect in-shuffles. Write a program to determine how many perfect out-shuffles it takes for a deck of 52 cards to return to its original order? How many perfect in-shuffles?
Answer: 8 and 52, respectively.
Perfect shuffling magic. Several card tricks rely on the magician to be able to perform perfect shuffles. Show that you can move the top card in a 52 card deck to any location by using the right combination of 8 perfect in-shuffles and out-shuffles. Write a program that takes a command line argument N (between 0 and 51) and performs 8 perfect shuffles so that the top card ends up in position N. Hint: consider N in binary (from left to right) and perform a perfect out-shuffle if the bit is 0, and a perfect in-shuffle if the bit is 1.
Out of fuel. Suppose that there are N fuel stations along the DC beltway. You need G gallons of fuel to drive around and the total amount of fuel available in all of the fuel stations is equal to G. You must drive in a counterclockwise direction. You start with 0 gallons. At which station should you start to make it around the beltway without running out of fuel? Assume the input is presented to you as a circular linked list, where each node contains a real number representing the amount of fuel at that station and the amount of fuel needed to get to the next station.
Doubly linked list. A doubly linked list. Use: fast deletion of objects other than front or back. Application: window manager stores a list of windows. When user clicks, their window comes to the front.
Doubly linked list deletion. Given a reference to a node in a doubly linked list, delete that node.
Postfix expression. Replace the toString method in ParseTree.java above with the following. What is the result of printing out the parse tree above.
public String toString() { if (s.equals("+") || s.equals("*")) return left + " " + right + " " + s; else return s; }
Infix expression. Rewrite the toString method in ParseTree.java so that it prints out the infix representation of the arithmetic expression using parentheses as needed, e.g, (((4 + 5) + (6 * 7)) * 8) for the parse tree above.
public String toString() { if (s.equals("+") || s.equals("*")) return "(" + left + " " + s + " " + right + ")"; else return s; }
Binary tree iterator. Create an iterator for binary trees so that you can iterate through the nodes of a binary tree in preorder. Use "threaded tree" or maintain a stack.
Prefix free codes. Many data compression schemes (including Huffman codes) are based on encoding a set of symbols using a variable number of bits. A code is called prefix free if no codeword is a prefix of another. For example, the first code below is prefix-free, but the second is not since A is a prefix of C.
A:01 B:10 C:0010 D:0000 A:01 B:10 C:010 D:0000
Write a program to read in a list of codewords and print true if it is prefix-free and false otherwise. Hint: build a trie (or sort).
LZW compression. Use binary trie for binary input.
Parse tree from postfix expression. Read in a postfix expression and create the corresponding parse tree. Read in the elements of the postfix expression one at a time. When you get an integer, create a parse tree of one node containing that integer and push it onto a stack. When you get an operator, pop two trees off the stack, create a tree with the operator as the root and the two trees as the children, then push this tree back onto the stack.

Tree shape. Write a static method that takes two tree references as inputs and determines whether they have the same tree shape and pointer structure.

public static boolean sameShape(Tree x, Tree y) {
    if (x == null && y == null) return true;   // both null
    if (x == null || y == null) return false;  // exactly one null
    return sameShape(x.left, y.left) && sameShape(x.right, y.right);
}

Tree copy constructor. Create a copy constructor that takes as input a reference to a tree and creates a (deep) copy of a new tree. Assume the input is not null.
// untested public Tree(Tree x) { item = x.item; if (x.left != null) left = new Tree(x.left); if (x.right != null) right = new Tree(x.right); }
Tree reconstruction. Given the preorder and level-order traversals of a binary tree (only the elements, not the null nodes), build the tree.
Tree reconstruction. Given the inorder and postorder traversals of a binary tree, build the tree.
Tree sum. Give a binary tree of integers and a target sum S, find a path from the root to a leaf whose values sum to exactly S or report that no such path exists.
Least common ancestor. Given two nodes in a family tree where each node points to two parents, find their least common ancestor.
Family tree. In a family tree each member has a reference to their two parents. Given a family tree and references to two members x and y, determine their genetic relationship. If x is on the path from y to the root then x is a parent, grand parent, great grand parent, etc of y. If y is on the path from x to the root, then x is a child, grand child, great grand child of y. Otherwise, to determine what form of cousin relationship the two family members have, we define lca(x, y) to be the least common ancestor of x and y. Now, x and y are kth cousins, jth removed, where j = |m-n|, k = min(m, n), m is the length of the path from x to lca(x, y) and n is the length of the path from y to lca(x, y). If j = k = 0, then x and y are siblings.
Single-link hierarchical clustering. Creates a dendrogram or taxonomy of points. Repeatedly find two closest points not in the same cluster and merge them. (Hierarchical agglomerative clustering.)
Geneological tree. Argue why a geneological tree (e.g., British royalty) is not a tree. Answer: inbreeding and overlap. This is inevitable since you would need exponentially many distinct people at level N.

Web Exercises and Unfinished Exercises

Windows manager. Use a linked lists of overlapping rectangles to model a bunch of open Windows. Allow the user to select a window and bring it to the front by moving that element to the beginning of the linked list. Here's a related Berkeley assignment.
Phylogenetic alignment. Given a tree T with distinct strings in each leaf, the phylogenetic alignment problem is to find an assignment of strings to the internal nodes of T that minimizes the sum of the edit distances between adjacent nodes. This phylogeny tree represents the evolutionary history of a set of species of interest and the differences between adjacent nodes represent mutations. Gusfield (p. 355) gives a dynamic programming heuristic that finds a provably good solution to this NP-hard optimization problem.

Zip code database. Create a database of US zip codes and town. There may be more than one zip code for a given town. Here is data from the 1990 Census. The format is: state Fips code, 5 digit zip code, USPS state abbreviation, town name, longitude (in decimal degrees, West is assumed with no minus sign), latitude (North is assumed with no plus sign), 1990 population, allocation factor (decimal portion of state within zipcode).

"34","08540","NJ","PRINCETON",74.640832,40.366633,33831,0.004376
"34","08542","NJ","PRINCETON",74.659378,40.353545,2675,0.000346
"34","08544","NJ","PRINCETON UNIVER",74.65754,40.346029,4227,0.000547
"34","08550","NJ","PRINCETON JUNCTI",74.614596,40.297684,5807,0.000751
"37","27569","NC","PRINCETON",78.167368,35.455833,5378,0.000811

Note that the same town name be appear in different states. See also the US Gazetteer.

Write a program that reads in two US zip codes and computes the approximate great circle distance between them. Given the latitude and longitude (L1, G1) and (L2, G2) of two points in degrees, the great circle distance is computed using spherical trigonometry:
D = 1.852 * 60 * arccos(sin(L1)*sin(L2) + cos(L1)*cos(L2)*cos(DG))
We assume 1 minute of arc is 1 nautical mile and 1 nautical mile is 1.852 km. All angles are in degrees.
Use data from the 2000 Census. The data format is: 5 digit zip code, followed by longitude, followed by latitude.
00210 71.0132 43.00589
Reference: this website. Variant: read in a zip code and compute all zip codes within 5 miles.
Something with states and area codes? Each state has one or more three digit area codes; some three digit area codes don't correspond to any state....