Recursion and Binary Trees 1

Example: Problem from second midterm, Fall 2018 2

Example: Second Midterm Spring 2019 5

Recursion and Binary Trees

Binary trees are inherently recursive: a tree is a single node with a left and right subtree. Since
the subtrees are also trees, we see a self-referential description of trees --- every node in a tree
has subtrees.

We see this in the simple method count above which returns the number of nodes in a tree.
This method counts 1 for the node that's the root of a binary tree -- the single parameter to the
method. The recursive calls each determine the count of the left and right subtrees,
respectively. As with most tree-methods, the code you write produces a result for a single node
--- the root --- and combines the results of recursive calls with that some value based on the root
node parameter. For the method count this means adding the results of the number of nodes
in the left and right subtrees to the 1 that represents the root. That's the entirety of line 171:
making two recursive calls and using the return values of each call to return a value.

This same pattern occurs repeatedly when writing tree methods: make two recursive calls and
combine the results of the calls with some value based on the root to produce a final result. This
is by far the most common pattern for tree recursion. As you think about writing a recursive
method for trees, keep these things in mind:

1. What are the base cases and how can you solve them without recursion?
2. How are the results of recursive call(s) used in creating the return result?
3. How do the recursive calls each make progress toward the base case?

In answering the second of these three questions, make sure that the value returned by
recursive calls are used and not ignored. Sometimes a void helper method is used, but typically
even helper methods return a value. Be sure you're thinking about the return value in
developing code to answer question 2. In answering question 2 you should almost always be
using some property of the root in creating the result result. In the count example this using +1.

1
Don't forget to check leaf nodes and internal nodes with one child as part of verifying that the
base case is correctly identified and used correctly in creating a return value.

Example: Problem from second midterm, Fall 2018

Read this problem (below, write maxPath) and think about developing a solution. We'll discuss
the development and the solution next. In thinking about a solution answer these questions,
copied from above:

1. What are the base cases and how can you solve them without recursion?
2. How are the results of recursive call(s) used in creating the return result?
3. How do the recursive calls each make progress toward the base case?

Read the problem statement carefully. It tells you that you must have base case for an
empty/null tree and that the return value is 0.

if (root == null) return 0;

2
Sometimes you should think of the leaf as another base case, or as using the results of two
calls on empty trees in a recursive setting. What's the maximal path for a tree consisting of a
single node? (think before reading)

It's the value of the node itself.

In verifying your recursive code, it's a good idea to consider such a tree (single node). If you
don't have a leaf as a base case, verify that the recursive calls work in constructing the return
value. In this example we won't add another base case, but we'll verify our solution with a
single-node (leaf) tree and discuss this below.

It's often a good idea to start with making recursive calls and storing the results in local
variables. This helps with the second of three questions. In this example the method has a
single TreeNode parameter, so the recursive calls and their return values could be written as

int leftMax = maxPath([Link]);

int rightMax = maxPath([Link]);

Almost all tree methods will need to make recursive calls for both the left and right subtrees.
Thinking about parameters and their types will help answer question 2: how are the results of
the recursive used in creating a return result?

In this case using the diagram may help. Consider the node N with a 4 that's in the left subtree
of the global root. For the tree with that root the left maxPath must be 3 (there's only one node)
and the right maxPath must be 4 (there's only one path to a leaf). What is the maxPath returned
for N? It must be 8, there's a path with that sum. Note that 8 is the value of 4+4: the node N's
value + the maximal of the left and right subtree results.

return [Link] + [Link](leftMax, rightMax);

This answers question 2 with code: how are the results of the two recursive calls used in
creating the return result? The largest of these is added to the value of the root to create a
return result.

Verify that this code works for leaf nodes like 6 and 9 in the diagram. What are the results
stored in leftMax and rightMax? Since the children of a leaf node are null, these results are
zero. The value returns is then the value in the leaf node ([Link]) + [Link](0,0) --- which is
exactly the correct value.

Before checking the global root, let's look at question 3: how do recursive calls get closer to the
base case? Since the base case is an empty or null tree, does a call with [Link] or
[Link] get closer to an empty tree? The answer is yes! Because the left and right
subtrees must have at least one fewer node that in the entire tree. So the number of nodes in
the tree decreases with each call, so each call gets closer to the base case of an empty tree.

3
We've checked leaves, let's check the global root. The maximal path in the left subtree is 14,
from 6-4-3-1. The maximal path in the right subtree is 16 from 2-1-4-9. This means the return
statement expression [Link](leftMax,rightMax) is [Link](14,16) which is 16.
The return value is then [Link] + 16 which is 18 -- the answer for the tree!.

In general we used each of the three questions, verifying the answer to the second question
with code and tracing the results for both leaf nodes and for non leaf nodes. Here's a succinct
version that uses the recursive calls directly as arguments to [Link]. This isn't better or more
efficient, it's just less to write.

(Another question on next page)

4
Example: Second Midterm Spring 2019
The problem below contains several diagrams that help make it clear what the recursive method
should return. In this problem a recursive helper method is used. We'll walk through the problem
and use the three questions to develop a solution.

As you'll see in the question below, you're asked to write a method that returns such a full tree.
The single parameter to the method is the number of levels. The call createFull(2) should
return the tree on the left and the call createFull(4) should return the tree on the right. As
you read and think about the code you'll write remember the three questions. We reproduce
them here.

1. What are the base cases and how can you solve them without recursion?
2. How are the results of recursive call(s) used in creating the return result?
3. How do the recursive calls each make progress toward the base case?

5
This problem is different since the helper method has two parameters. You should think about
what each parameter is used for. The base case provides a hint. When creating a single node
tree, with no children, the parameter nodeValue is stored in the single node returned. That might
be 2 or 3 for the tree on the left or 8, 9, 10, 11, 12, 13, 14, or 15 for the tree on the right. These
are the only nodes with no children, as single nodes they're at level 1 since they have no
children. Think about this and keep it mind as we turn to question 2: How are results of the
recursive calls used in creating the return result?

This is a method that returns a tree. Trees consist of a root node that has a value and two
subtrees. You should think about the value stored in the root returned, and how to use the
results of the recursive calls in creating the tree returned. The return type helps here: TreeNode.
That means your code will need to create and return a TreeNode -- with a value and two
subtrees.

TreeNode leftSub = …
TreeNode rightSub = …
TreeNode ret = new TreeNode( …., leftSub, rightSub);
return ret;

6
This is the form called for by question 2: how are the results of the recursive calls use to create
the return result?

In this case the recursive calls create subtrees. Use the types of the method to help in
determining that these trees are the left and right subtrees of the single node created. For
example, in the tree on the left above? These will store leaf nodes, single-node trees with the
values 2 and 3 for left and right, respectively. These will be the left subtree of the root: whose
value is 1. That helps in determining that the TreeNode created in the non-base case also uses
parameter nodeValue as the value stored in the root returned. Each parameter has a purpose,
The comment of the method helps! It indicates that nodeValue is the value stored in the
returned tree's root. The code we have now looks like the following, where we've sketched in
the recursive calls used in creating the tree returned. We have to fill in these values using the
diagrams above and the answer to question 3: how do recursive calls make progress toward the
base case. We'll use the call that generates the tree on the right to help here. That tree is
returned by the call createFull(4). This generates the helper method call
fullHelper(1,4) -- make sure you've verified this in the code above.

TreeNode leftSub = fullHelper(..., ...);

TreeNode rightSub = fullHelper(..., ...);
TreeNode ret = new TreeNode(nodeValue, leftSub, rightSub);
return ret;

The diagrams above will help in determining the first argument in the recursive calls. For the
global root, which is 1, the root of the left-subtree is 2 and the right-subtree is 3. Pick any node
in the tree and look at the value of its left and right children. Is there a pattern? For every node,
the left child is always twice the value of its parent and the right child is always one more than
than twice the value of its parent. Think about this pattern carefully and remember that the first
parameter, nodeValue, is used to create the value in the root of the tree returned. This helps
complete the recursive calls, though we're not quite done.

TreeNode leftSub = fullHelper(nodeValue * 2, ...);

TreeNode rightSub = fullHelper(nodeValue * 2 + 1, ...);
TreeNode ret = new TreeNode(nodeValue, leftSub, rightSub);
return ret;

Thinking about the second parameter and the third question will help as you write/create the
recursive calls. If the top-level helper method has levels == 4, how many levels will there be in
the left and right subtrees? Think about why the answer must be 3. In general, when the helper
method is called with the second parameter having levels == N, the two subtrees created will
have one less level. For example, when create(2) is called to create the tree on the left, the
helper method call is fullHelper(1,2) -- this must create two subtrees that are leaves, that is in
which the value of levels is 1. This leads to the calls below.,

TreeNode leftSub = fullHelper(nodeValue * 2, levels-1);

7
 TreeNode rightSub = fullHelper(nodeValue * 2 + 1, levels-1);
TreeNode ret = new TreeNode(nodeValue, leftSub, rightSub);
return ret;

Note that answers question 3: since the value of levels is decreasing, eventually the base case
of 1 is reached. You should verify that these calls work by using some nodes in the tree on the
right above. The calls fullHelper(2,3) and fullHelper(3,3) are made by the original
call of fullHelper(1,4). What calls do these make? The first will call fullHelper(4,2)
and fullHelper(5,2) -- verify to yourself that these are correct for the subtrees of the node
whose value is 2.

In thinking about the recursive calls, always think about the types of each parameter and how
the value returned by the recursive calls is used. These are part of answering question two.
Ultimately this leads to the succinct answer below. You think about why this code is correct, how

the three questions are answered, and to be sure? You should re-write the solution without
looking at the code, but by remembering the three questions.