Lab 8: Binary Search Tree Count

Objective

To gain experience with binary search trees.

Task

One method that we don't currently have in our binary search tree is one that tells us how many nodes we are storing. It might be helpful to know how many pieces of data our data structure contains.

One possible way of doing this is creating an integer that stores the number of elements, incrementing and decrementing it at the right times.

Instead however, you should write a method that counts the number of nodes in the tree without needing to store it as a member variable. This is most easily done using recursion.

Details

• Start by downloading BinarySearchTree.java which contains a copy of the binary search tree class we were working with in class.
• Add a method called count() which returns an integer giving the number of nodes in the tree. Remember this should be done recursively.
• You will need to add another helper method that takes no parameters and calls your recursive method starting at root, like the insert and search methods do.
• You can use CountTest.java to test your program. The sample tree in the program has 10 nodes.

Submitting

When you're finished, please submit your code for this lab on Canvas.