Tree Exercises

This homework will focus on writing algorithms to recursively traverse and manipulate binary trees.

You will be using an online tool called CodeWorkout to complete these exercises. Creating an account is optional, but it will allow you to track your progress and save your work. Final submission will be through Gradescope. As you complete each exercise, you can copy your working code into the following template file:

TreeAnswers.java

BinNode Interface

These exercises utilize a BinNode interface that represents a node in a binary tree. Here are the available methods:

classDiagram
direction BT

class BinNode {
<<interface>>
    +value() int
    +setValue(v: int)
    +left() BinNode
    +right() BinNode
    +isLeaf() boolean
}

The value methods should be straight-forward. The left() and right() methods return a reference to the left and right child of the node, respectively. The isLeaf() method returns true if the node is a leaf node (i.e., it has no children).

Warmup

Start with this exercise (solution is available if needed):

• Binary Tree Sum Nodes

The problem will want you to make your solution as "elegant" as possible. You shouldn't need to call isLeaf(), nor do you need to check if the left or right child is null.

Hints

• Start with the base case:
  • If the BTsumall method is called with a null node, return 0.
• If we had the sum of the left and right subtrees, that would help us solve the problem!
  • Trust that the recursive calls will work, then call them.
  • As long as your base case is correct, the recursive calls will eventually reach the base case.
• What should you return after the recursive calls?
  • Add the current node's value to the sum of the left and right subtrees.

Solution

public int BTsumall(BinNode root)
{
    if (root == null) {
        return 0;
    }

    int leftSum = BTsumall(root.left());
    int rightSum = BTsumall(root.right());

    return root.value() + leftSum + rightSum;
}

Remaining Exercises

Afterwards, complete the following exercises (recommended in this order):

• Binary Tree Leaf Nodes Count

• Binary Tree Set Depth

• Binary Tree Height

• Structurally Identical Binary Trees

• Mirror Image Binary Trees

General Tips

• Read the problem carefully. Make sure you understand what the problem is asking for before you start writing code.
• Draw a picture of the tree. This can help you visualize the problem and come up with a plan.
• These will all require recursive solutions!
  • Start with a base case. What is the simplest form of the problem with a known solution?
  • Make recursive calls. What can you do with the result of those calls? Trust that the recursive calls will work and use their results to solve the current step of the problem.

Submission

Submit your completed version of TreeAnswers.java through Gradescope.