Finding A Value In The Tree
The goal for this
exercise
is to implement the
binary search tree’s Find method, in C# source code.
What you need to do for
this exercise:
- In the provided starter
solution, in the file named Student_Answers.cs, there is a class named
BinarySearchTree. For this exercise, you should implement the ‘Find’ method,
as described in the online lecture.
- The Find has one
parameter: an int - the value to search for.
It should return true if the specified value is present, and false otherwise.
For right now, follow the lecture’s example and use an interative (loop-based)
solution. In a future exercise you will re-implement this method using a
recursive approach)
- You should be able to
accomplish this by modeling your code off of what you saw in class, although I'd
recommend doing as much of this from memory as possible.
- Once you’ve completed the above tasks,
you should test out your code in order to make sure that it works.
- A good way to
test your find routine would be to walk through your test code using the
debugger.
- Another good way to
test your insert routine would be to create a PrintTree routine, and have it
print everything in your binary search tree, using an pre-order traversal.
This won’t give you a perfect picture of the structure of the tree, but it’s
better than the normal in-order traversal (which prints out everything in order,
regardless of the structure of the tree).
We haven’t covered this yet, though, so you are NOT required to do this part of
the exercise.
- Once you’ve completed the above task, you should run the tests in
the
NUnit_Tests_BST_Find_Iterative
class. They should all
pass at this point, and if not, then you should fix your program so that
those tests do pass. You can run the tests using the NUnit support in
the provided starter project.