The BST Rule and Searching

A tree with a rule

A binary search tree (BST) is a binary tree with one simple rule for every node:

• everything in its left subtree is smaller,
• everything in its right subtree is bigger.

#          8
#        /   \
#       3     10
#      / \      \
#     1   6      14
class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

root = Node(8, Node(3, Node(1), Node(6)), Node(10, None, Node(14)))

def search(node, target):
    steps = 0
    while node:
        steps += 1
        if target == node.value:
            return True, steps
        node = node.left if target < node.value else node.right
    return False, steps

print(search(root, 6))
print(search(root, 7))

Output

(True, 3)
(False, 3)

Think of it like this: It's binary search, but built into the shape of the data. At each node you ask “smaller or bigger?” and throw away the other half of the tree.

Searching takes as many steps as the tree is tall: O(height). For a nicely balanced tree with n nodes, the height is about log₂ n.