Trees and Recursion
> Click or hit ControlEnter to run Example.main above
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

I have office hours today from 1–2PM. Please come by!

As a reminder we have midterm preparation office hours today from 11AM–9PM. As usual, the calendar is uptodate.

We’ve added an anonymous feedback form to the course website. Use it to give us feedback!