More Practice with Recursion
> Click or hit ControlEnter to run Example.main above
Welcome Back!
I hope you all had a restful weekend.
Recursive Tree Print Leaves
Let’s print only leaf nodes: those that have neither a left nor a right child.
What’s Our (Recursive) Algorithm?
Recursive Tree Print Leaves

Base case: We’ve reached a tree with no left or right node. It’s also a a leaf node, so print our value.

Recursive step: Consider our right tree and left tree separately.

Combine results: Nothing to do here, just continue down the tree.
> Click or hit ControlEnter to run Example.main above
Writing Perfect Code
Starting today we’ll be assigning a small amount of credit on each homework problem for writing "perfect" code.
Obviously we can’t tell whether your code is really perfect 1—meaning correct, beautiful, minimal, concise, readable. But for the purposes of automated checking we will consider your code not to be perfect if:

It contains dead or unreachable code.

It is overly complex compared to our solution.
Dead Code
public class YourBinaryTree extends BinaryTree {
public int size() {
return size(root);
}
private int size(Node current) {
if (current == null) {
return 0;
}
if (current != null) {
return 1 + size(current.left) + size(current.right);
} else {
return 0;
}
}
}

The last
return 0
will never be reached!
High Complexity
public class YourBinaryTree extends BinaryTree {
public int size() {
return size(root);
}
private int size(Node current) {
if (current == null) {
return 0;
}
if (current.left == null) {
return 1 + size(current.right);
} else if (current.right == null) {
return 1 + size(current.left);
} else {
return 1 + size(current.right) + size(current.left);
}
}
}

There are 5 paths through
size(Node current)

For the solution there are only 2.
Questions About Perfection?
Recursive Tree Search
Let’s determine whether a tree contains a certain value.
What’s Our (Recursive) Algorithm?
Recursive Tree Search

Base case: We’ve reached a node with no descendants. Return true if its value matches, zero otherwise.

Recursive step: Consider our right tree and left tree separately.

Combine results: Return true if either we or our right or left subtree contain the search value.
> Click or hit ControlEnter to run Example.main above
How Could We Make This Search More Efficient?
> Click or hit ControlEnter to run Example.main above
Other Recursive Data Structures
Every sub(blank) of a (blank) is, itself, a (blank).

Tree

(Contiguous) List

(Contiguous) Array