Trees · routine

Search a binary search tree

In a binary search tree every value on the left of a node is smaller than it and every value on the right is bigger. Write contains(root, target).

You never need to look at both sides: one comparison tells you which way to go.

right answers
arguments left as they should be
fast enough at scale

Already written for you — you can use these

1class TreeNode:
2    def __init__(self, value, left=None, right=None):
3        self.value = value
4        self.left = left
5        self.right = right
6 
7def bst(values):
8    """A balanced binary search tree holding the sorted values."""
9    if not values:
10        return None
11    mid = len(values) // 2
12    return TreeNode(values[mid], bst(values[:mid]), bst(values[mid + 1:]))

def contains(root, target):
    if root is None:
        return False
    if root.value == target:
        return True
    return contains(root.left, target) or contains(root.right, target)

Run adds print(contains(bst([1, 3, 5, 7, 9]), 7)) after your code, to try it.

Stuck on the idea rather than the code? The Trees lesson walks through it.