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