Create a method sameShape
that accepts two BinaryTree<*>
arguments and returns true if they have the same
shape and false otherwise.
Two binary trees have the same shape if they have the same nodes in the same positions, regardless of the values
that each node contains.
Because the trees passed to sameShape
are non-null
, you should set up a private helper function to actually
perform the recursion, allowing you to handle null
as a base case.
You can provide a second method next to your sameShape
using the private
keyword to mark it as private.
For example:
In this problem you'll perform recursion on both trees at the same time.
But in every other way it's a typical tree recursion problem.
Consider your base case: if you reach a null
subtree for both trees in the same step, then they have the same
shape at that point in the tree.
Otherwise, consider the other cases and how to handle them, as well as how to
continue the recursion and combine the results from your recursive steps together.
For reference, cs125.trees.BinaryTree
is defined like this:
Stuck? You may find these lessons helpful: