Write a recursive method sum that takes a
BinaryTree and returns the int sum of all the
values in it. The sum of the empty tree (null) is
0.
Write a recursive method size that takes a
BinaryTree and returns the number of nodes in it. The empty
tree has size 0; a leaf has size 1.
Write a recursive method depth that takes a
BinaryTree and returns the number of nodes on the longest
path from the root down to a leaf. The empty tree has depth
0, a leaf has depth 1, and otherwise the depth
is one more than the depth of the deeper child.
Write a recursive method contains that takes a
BinaryTree and an int target and
returns a boolean indicating whether any node in the tree
has that value. The empty tree contains nothing.
Write a recursive method countLeaves that takes a
BinaryTree and returns the number of leaves in it. A leaf is
a tree with both children null. The empty tree has no leaves.
Write a recursive method mirror that takes a
BinaryTree and returns a new BinaryTree that is
its mirror image: the same values, but with left and right swapped at
every node. The mirror of the empty tree is the empty tree. Build the
result with the BinaryTree constructor; the trees you are
given can’t be modified.
Write a recursive method nodeCount that takes a
Tree and returns the number of nodes in it. A leaf is
1 node; any other node counts as one plus the nodes in each
of its children.
Write a recursive method height that takes a
Tree and returns the number of nodes on the longest path
from the root down to a leaf. A leaf has height 1;
otherwise the height is one more than the height of the tallest child.
Write a recursive method maxValue that takes a
Tree and returns the largest value anywhere in it. Since a
Tree is never empty, there is always an answer.
Write a recursive method occurrences that takes a
Tree and an int target and
returns the number of nodes in the tree with that value.
Write a recursive method mostChildren that takes a
Tree and returns the largest number of children any one node
in the tree has.
Write a recursive method sumAtDepth that takes a
Tree and an int depth and returns
the sum of the values of the nodes at exactly that depth, where the root
is at depth 0, its children are at depth 1, and
so on. If the depth is deeper than the tree’s height,
return 0.
Recursion over trees. A tree is a recursive data structure made up of other
trees. This assignment uses two different kinds of trees, but in both each
tree object holds an int value and also has child trees. The
starter code imports both tree classes for you. The objects are immutable as
is common when writing recursive methods.
A BinaryTree has an int value and at most two
children. value() returns the value, and left()
and right() return the children, each of which is either
another BinaryTree or null. A null
represents an empty tree with no value and no children. Thus
a BinaryTree whose whose children are both null is
a leaf. Note that a method that takes a BinaryTree argument
should handle null as the representation of an empty tree. You
can construct a BinaryTree with new BinaryTree(value,
left, right) or
new BinaryTree(value) for a leaf. (You can also make a leaf
with new BinaryTree(value, null, null).)
A Tree has an int value and any number of
children. value() returns the value and
children() returns a List<Tree> of the
children, in order. children() always returns a non-null value,
which will be an empty list for a leaf. A Tree argument should
never be null: there is always at least one node with one
value.
In the test results a tree is written in a compact form: a leaf is just its
value, and any other node is its value followed by its children in
parentheses, with . for a missing child in a binary tree.
So (5 3 (8 . 9)) is the binary tree whose root is
5, with a leaf 3 on the left and on the right a
node 8 with no left child and a leaf 9 on the
right. And (5 3 (8 9 2) 1) is the general tree whose root
5 has three children: the leaf 3, a node
8 with two leaf children, and the leaf 1.
The BinaryTree methods have exactly two children to recurse on,
so they need no loops at all, and none are allowed. For the methods
on Tree you may use a loop to iterate over a node’s children
but the method must still be recursive. Or if you really want you can
recurse over the list too, with a helper.