A Common-Sense Guide to Data Structures and Algorithms

Searching

Here again is a binary tree:

The algorithm for searching within a binary tree begins at the root node:

1. Inspect the value at the node.
2. If we’ve found the value we’re looking for, great!
3. If the value we’re looking for is less than the current node, search for it in its left subtree.
4. If the value we’re looking for is greater than the current node, search for it in its right subtree.

Here’s a simple, recursive implementation for this search in Python:

def search(value, node):
    # Base case: If the node is nonexistent
    # or we've found the value we're looking for:
    if node is None or node.value == value:
        return node