Next we’ll continue practicing with trees and recursion! And what better way to do that then to do a few problems together? So let’s get started!
As a warm up, let’s do another counting problem.
Given a binary tree containing Integer
s, let’s count the number of nodes where the value of the left child is greater than the value of the right child.
Before we start, remember the core of our approach to recursion:
Next, we’ll look at how to determine if a binary tree contains a certain value. This problem introduces a new wrinkle to our usual approach to recursion!
Create a public class BinaryTreeCounter
that provides a single class method named countEqualToEitherChild
that
accepts a single BinaryTree
and counts the number of nodes in the tree where the value at that node is equal to
either the value at its right child or the value at its left child. Keep in mind that not every node has a
right or left child, so you'll need to check for null
carefully. (Or use try-catch
!) However, you can assume
that all of the values in the tree are non-null.
For reference, cs125.trees.BinaryTree
has the following public properties:
Next, let’s examine the performance of our recursive algorithms, and determine what O(n) category they belong in.
Create a public class BinaryTreeCounter
that provides a single class method named countEqualChildren
that
accepts a single BinaryTree<?>
and counts the number of nodes in the tree that have two children with equal
values.
Keep in mind that not every node has a right or left child, so you'll need to check for null
carefully.
(Or use try-catch
!)
However, you can assume that all the values in the tree are non-null.
For reference, cs125.trees.BinaryTree
has the following public properties:
Need more practice? Head over to the practice page.