Lesson 8 of 14

Search Trees and Balance

Must a tree search inspect every node? Placing smaller values to the left and larger values to the right lets us skip one side. This is the basic rule of a binary search tree (BST). Assume there are no duplicate values in this lesson.

The rule covers entire subtrees

At each node, every value in its left subtree is smaller, and every value in its right subtree is larger. Comparing only immediate children is insufficient.

      40
     /  \
   20    60
  /  \
 10  30

Searching for 30 follows 40 → 20 → 30: left because 30 is below 40, then right because it exceeds 20. The side containing 60 is skipped.

Search in code

tree = (40, (20, (10, None, None), (30, None, None)),
        (60, None, None))

def contains(node, target):
    while node is not None:
        value, left, right = node
        if target == value:
            return True
        node = left if target < value else right
    return False

print(contains(tree, 30))
print(contains(tree, 50))

This prints True, then False. The search takes O(h), where h is the tree’s height.

Why balance matters

Inserting 10, 20, 30, 40 in order can create a one-sided chain resembling a linked list. Its height approaches n, making worst-case search O(n). A binary tree does not automatically give O(log n) search.

An AVL tree keeps the heights of each node’s left and right subtrees within one of each other. Rotations adjust links after insertions or deletions upset that balance. Maintaining balance gives O(log n) search, insertion, and deletion.

A B-tree stores multiple keys per node and is used with storage that reads data in blocks. A threaded tree instead uses otherwise empty child references to assist traversal. Identify the cost each variation aims to reduce.

Check your understanding

Would placing 45 as the right child of 20 make the pictured tree a valid BST?