A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Searching

Here, again, is a binary search tree:

The algorithm for searching within a binary search tree is as follows:

1. Designate a node to be the “current node.” (At the beginning of the algorithm, the root node is the first “current node.”)

2. Inspect the value at the current node.

3. If we’ve found the value we’re looking for, great!

4. If the value we’re looking for is less than the current node, search for it in its left subtree.

5. If the value we’re looking for is greater than the current node, search for it in its right subtree.

6. Repeat Steps 1 through 5 until we find the value we’re searching for, or until we hit the bottom of the tree, in which case ...