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

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

Worked Example

Search for 6 in this BST:

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

Step	Current Node	Comparison	Action
1	8	6 < 8	Go left
2	3	6 > 3	Go right
3	6	6 == 6	Found!

Number of comparisons: 3 (compared with O(n) = 9 for linear search)

Time Complexity

Case	Complexity	When
Best	O(1)	Value is at the root
Average	O(log n)	Tree is reasonably balanced
Worst	O(n)	Tree is degenerate (all nodes on one side)

---

Insertion in a BST

Insertion always adds a new node as a leaf — it never restructures the existing tree.

Algorithm

1. Start at the root.
2. If the tree is empty, the new node becomes the root.
3. Compare the new value with the current node:
   • If less, go to the left child.
   • If greater, go to the right child.
4. When you reach a null pointer (empty position), insert the new node there.

Pseudocode (OCR Style)

function insert(node, value)
    if node == null then
        node = new TreeNode(value)
        return node
    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 Implementation

def insert(node, value):
    if node is None:
        return TreeNode(value)
    if value < node.data:
        node.left = insert(node.left, value)
    elif value > node.data:
        node.right = insert(node.right, value)
    return node

Worked Example

Insert 5 into this BST:

       8
      / \
     3   10
    / \
   1   6

Step	Current Node	Comparison	Action
1	8	5 < 8	Go left
2	3	5 > 3	Go right
3	6	5 < 6	Go left
4	null	-	Insert 5 here

Result:

       8
      / \
     3   10
    / \
   1   6
      /
     5

---

Deletion from a BST

Deletion is the most complex BST operation because removing a node must preserve the BST ordering property. There are three cases.

Case 1: Deleting a Leaf Node (No Children)

Simply remove the node by setting its parent's pointer to null.

Example: Delete 1 from the BST:

Before:          After:
    8                8
   / \              / \
  3   10           3   10
 / \              / \
1   6            _   6

Case 2: Deleting a Node with One Child

Replace the node with its only child. The child takes the deleted node's position.