Trees and Recursion
> Click or hit ControlEnter to run Example.main above
LinkedList
Insertion Algorithm

Find the right spot.

Set the reference on the preceding item to point to the new item.

Set the reference on the new item to point to the former next item.
Insertion Example
Let’s insert value 7 at index 1.
Insertion Example
Let’s insert value 7 at index 1.
But wait, now we can’t change the preceding reference.
Insertion Example
Let’s insert value 7 at index 1.
Insertion Example
Let’s insert value 7 at index 1.
Insertion Example
Let’s insert value 7 at index 1.
Insertion Example
Let’s insert value 7 at index 1.
Singly Linked Lists
public class SimpleLinkedList {
class Item {
Object value;
Item next;
Item(Object setValue, Item setNext) {
value = setValue;
next = setNext;
}
}
private Item start;
}
What we’ve been discussing is known as a singly linked list.
Doubly Linked Lists
public class SimpleDoublyLinkedList {
class Item {
Object value;
Item next;
Item previous;
Item(Object setValue, Item setNext) {
value = setValue;
next = setNext;
}
}
private Item start;
private Item end;
}
You can also have both forward and backward links. This is known an a doubly linked list.
Doubly Linked Lists
public class SimpleDoublyLinkedList {
class Item {
Object value;
Item next;
Item previous;
Item(Object setValue, Item setNext) {
value = setValue;
next = setNext;
}
}
private Item start;
private Item end;
}
Time v. Space
public class SimpleArrayList {
private Object[] array;
}
public class SimpleDoublyLinkedList {
class Item {
Object value;
Item next;
Item previous;
}
private Item start;
private Item end;
}
ArrayList
v. LinkedList
also represents a time v. space tradeoff.

LinkedList
is faster for certain operations… 
but consumes more space to store the same amount of information.
Time v. Space
public class SimpleArrayList {
private Object[] array;
}
public class SimpleDoublyLinkedList {
class Item {
Object value;
Item next;
Item previous;
}
private Item start;
private Item end;
}
To store n int
s:

ArrayList
: nvalue
s 
LinkedList
: 3n (1value
, 1next
, 1previous
)
ArrayList
v. LinkedList
Both provide the same functionality, but with different performance characteristics.
Operation  ArrayList 
LinkedList 


O(n) 
O(1) 

O(1) 
O(n) 

O(n) 
O(n) 
Questions About Lists?
Onward! Trees
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.
Trees: Parent and Child
Each parent has one or more children.
Trees: Parent and Child
Each parent has one or more children. Each child has one parent.
Trees: Root and Leaves
We refer to the top of the tree as the root.
Trees: Root and Leaves
We refer to the top of the tree as the root. We refer to nodes without any children as leaves.
Trees: Level and Depth
We can enumerate each level in a tree starting with the root as 0.
Trees: Level and Depth
We can enumerate each level in a tree starting with the root as 0.
Trees: Level and Depth
We can enumerate each level in a tree starting with the root as 0.
Trees: Level and Depth
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.
What Are Trees For?
What kinds of data can we represent using trees?

The Java class hierarchy 1

Files on your computer

Domain names on the internet

Any data that has a hierarchical structure.
Java Class Hierarchy
public class Pet { }
public class Dog extends Pet { }
public class Cat extends Pet { }
public class OldDog extends Dog { }
Your Computer’s Files
$ cd / && ls l
System
Library
Users
$ cd Users && ls l
challen
Shared
$ cd challen && ls l
classes
www
Domain Name Translation
Binary Trees
A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.
public class Tree {
Object value;
Tree right;
Tree left;
}
We are rarely interested in trees only for their structure. Usually we use them to structure data.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Subtrees As Trees
Every subtree of a tree is, itself, a tree.
Recursion
Recursion occurs when a thing is defined in terms of itself or of its type.
public class Tree {
Object value;
Tree right;
Tree left;
}
Recursion in Computer Science
Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem.
Recursion v. Iteration
So far we’ve pursued iterative algorithms in this course. Recursion provides us with a new way to approach problems.

Iteration: repeat the same set of steps over and over again

Recursion: break a larger problem into smaller problems until they are small enough to solve easily
Tree Node Counting
Let’s say that we wanted to count the number of nodes in the tree above.
Iterative Node Counting
We can count iteratively:

Visit every node in the tree

Increment a counter by 1 each time
Iterative Node Counting
We can count iteratively:

Visit every node in the tree

Increment a counter by 1 each time
Iterative Node Counting
We can count iteratively:

Visit every node in the tree

Increment a counter by 1 each time
Iterative Node Counting
We can count iteratively:

Visit every node in the tree

Increment a counter by 1 each time
Iterative Node Counting
We can count iteratively:

Visit every node in the tree

Increment a counter by 1 each time
Iterative Node Counting
We can count iteratively:

Visit every node in the tree

Increment a counter by 1 each time
Iterative Node Counting
We can count iteratively:

Visit every node in the tree

Increment a counter by 1 each time
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
Recursive Node Counting
We can count recursively:

Break the problem into smaller subproblems

Solve the smallest subproblem

Combine the results
> Click or hit ControlEnter to run Example.main above
Announcements

Good luck on the midterm!

I don’t have office hours today, but we have them as normally scheduled from 12–8PM in Siebel 0403.