Binary search trees

Binary search trees

• A binary search tree (BST) stores values so they stay sorted and are fast to find.
• Each node holds a value and links to up to two children: a left and a right.
• The top node is the root. A node with no children is a leaf.

The BST rule

• For every node: everything in its left subtree is smaller, everything in its right is larger.
• This one rule is what lets you find a value by going left or right — never both.

        5
       / \
      3   8
     / \   \
    1   4   9

left < node < right, at every node

A node

• We model a node as a small object with a value, a left, and a right.
• A brand-new node has no children yet, so left and right start as None.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

n = Node(5)
print(n.value)   # 5
print(n.left)    # None

Inserting a value

• Start at the root. If the tree is empty, the new value becomes the root.
• If the value is smaller than the current node, go left; otherwise go right.
• Repeat until you reach an empty spot, and put the new node there.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

root = None
for v in [5, 3, 8, 1]:
    root = insert(root, v)
print(root.value)            # 5
print(root.left.value)       # 3
print(root.right.value)      # 8

In-order traversal gives sorted order

• In-order traversal visits: the left subtree, then the node, then the right subtree.
• Because of the BST rule, this visits the values in sorted order — for free.
• It is naturally recursive: traverse left, take the value, traverse right.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

def in_order(root):
    if root is None:
        return []
    return in_order(root.left) + [root.value] + in_order(root.right)

root = None
for v in [5, 3, 8, 1, 4]:
    root = insert(root, v)
print(in_order(root))   # [1, 3, 4, 5, 8]

Searching is fast

• To find a value, compare it with the node, then go left or right — skipping half the tree each step.
• In a balanced tree this takes about O(log n) steps, much faster than scanning a list.
• A badly-shaped tree (values inserted already sorted) can degrade to a line — O(n).

Now you try

• Build the three core operations: insert, in_order, and contains.
• The Node class (and a working insert, where you need it) is provided.
• Press Check answer to test it on several trees.