Binary Search Trees

This lesson covers the Binary Search Tree (BST) — a specialised binary tree that maintains elements in sorted order, enabling efficient searching, insertion, and deletion. BSTs are a core topic in A-Level Computer Science.

---

What is a Binary Search Tree?

A Binary Search Tree is a binary tree with the following ordering property:

For every node N:

• All values in the left subtree of N are less than N's value.
• All values in the right subtree of N are greater than N's value.

This property holds for every node in the tree, not just the root.

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

For node 8: all left subtree values (1, 3, 4, 6, 7) < 8, and all right subtree values (10, 13, 14) > 8.

---

Searching a BST

To search for a value in a BST:

1. Start at the root.
2. If the target equals the current node's value, the search is successful.
3. If the target is less than the current value, move to the left child.
4. If the target is greater than the current value, move to the right child.
5. If you reach a null pointer, the value is not in the tree.

Pseudocode

FUNCTION search(node, target) RETURNS BOOLEAN
    IF node = NULL THEN
        RETURN FALSE
    ELSE IF target = node.data THEN
        RETURN TRUE
    ELSE IF target < node.data THEN
        RETURN search(node.left, target)
    ELSE
        RETURN search(node.right, target)
    END IF
END FUNCTION

Python

def search(node, target) -> bool:
    if node is None:
        return False
    if target == node.data:
        return True
    elif target < node.data:
        return search(node.left, target)
    else:
        return search(node.right, target)

Search Trace

Searching for 6 in the BST above:

1. Compare 6 with root (8): 6 < 8 → go left
2. Compare 6 with 3: 6 > 3 → go right
3. Compare 6 with 6: found!

Only 3 comparisons needed for a tree with 8 nodes.

---

Time Complexity

Operation	Average Case	Worst Case
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

The average case assumes a balanced tree where each comparison eliminates half the remaining nodes (like binary search on a sorted array).

The worst case occurs when the tree is degenerate (skewed) — essentially a linked list, requiring n comparisons.

Balanced BST (O(log n)):       Degenerate BST (O(n)):
        8                       1
       / \                       \
      3   10                      3
     / \    \                      \
    1   6    14                     6
                                     \
                                      8

Exam Tip: When discussing BST performance, always mention both the average (O(log n)) and worst (O(n)) cases. Explain that the worst case occurs when elements are inserted in sorted order, creating a degenerate tree.

---

Inserting into a BST

To insert a new value:

1. Start at the root.
2. Compare the new value with the current node.
3. If smaller, go left; if larger, go right.
4. When you reach a null pointer, insert the new node there.

Pseudocode

FUNCTION insert(node, value) RETURNS NODE
    IF node = NULL THEN
        RETURN NEW TreeNode(value)
    END IF
    IF value < node.data THEN
        node.left = insert(node.left, value)
    ELSE IF value > node.data THEN
        node.right = insert(node.right, value)
    END IF
    RETURN node
END FUNCTION

Python