Tree Operations

This lesson covers the core operations on Binary Search Trees (BSTs) — insertion, deletion, and searching — as required by the OCR A-Level Computer Science (H446) specification. These operations are fundamental to understanding how tree-based data structures work.

---

Searching in a BST

To search for a value in a BST, start at the root and use the ordering property to decide whether to go left or right.

Algorithm

1. Start at the root.
2. If the current node is null, the value is not in the tree.
3. If the value equals the current node's data, the value is found.
4. If the value is less than the current node's data, search the left subtree.
5. If the value is greater than the current node's data, search the right subtree.

Pseudocode (OCR Style)

function search(node, value)
    if node == null then
        return false
    end if
    if value == node.data then
        return true
    else if value < node.data then
        return search(node.left, value)
    else
        return search(node.right, value)
    end if
end function

Python Implementation