Test Writing: Binary Tree Search Path

Created By: Geoffrey Challen

/ Version: 2020.11.0

Let's continue exploring recursion on binary trees. However, this problem takes a significant step forward in difficulty, so be prepared!

We've provided a method pathToValue that accepts a BinaryTree<Any> as its first parameter and an Any as its second. It returns a List<Any> containing all the values in the tree on the way to the first node with a value equal to the passed Any, or null if the tree does not contain the passed Any. We've handled this case already for you in the starter code.

Our wrapper method initializes the list properly and then calls a private helper method which performs the recursion. The helper should return true if the tree contains the value, and if it does also manipulate the list properly. If the tree does not contain the value it should return false. You will want to use add(int index, Any value) to add values to the front of the list as you work your way through the tree.

This problem is hard! Here's an outline of a solution to help get you started:

• If you reach an empty tree, you can return false, since an empty tree does not contain the value
• Otherwise, if this node contains the value, add yourself to the list, stop recursing, and return true.
• Otherwise, first search your right subtree. If that succeeds, then this node is also part of the path and should be added. If not, try the left subtree.
• If neither the right nor left subtree contains the node, you should return false and not modify the list, since this node is not on the path to the desired node.

Good luck and have fun!

Test Design Challenge

You're challenge is to write tests for this problem described above.

• Provide a public class named TestBinaryTreePath with a single non-private class method named test that accepts no arguments and does not return a value.
• If the implementation of the class described above is incorrect, your test method should throw an exception.
• If it is correct, do not throw an exception.
• You may want to use Kotlin's assert or check methods