Binary Search Tree Operations — Insert, Search and Traverse (GCSE)

What is the BST ordering rule?

For any node N in a binary search tree:

• every value in N's left subtree is less than N's value.
• every value in N's right subtree is greater than N's value.

        50
       /  \
     30    70
    /  \   /  \
  20   40 60   80

Check: 30 is left of 50 (30 < 50 ✓). 40 is right of 30 (40 > 30 ✓). 60 is left of 70 (60 < 70 ✓). The whole tree satisfies the BST rule.

How do you insert a value into a BST?

Insertion starts at the root and follows the ordering rule down the tree until an empty slot is found:

• If the new value is less than the current node, go left.
• If the new value is greater than the current node, go right.
• If you reach a None pointer, insert the new node there.

Example: insert 45 into the tree above

• Start at 50: 45 < 50 → go left to 30.
• At 30: 45 > 30 → go right to 40.
• At 40: 45 > 40 → go right — empty slot found.
• Insert 45 as 40's right child.

        50
       /  \
     30    70
    /  \   /  \
  20   40 60   80
          \
          45

Trace table for inserting 45:

How do you search for a value in a BST?

Searching follows the same path as insertion:

• If the current node's value equals the target: found.
• If the target is less than the current node: search the left subtree.
• If the target is greater than the current node: search the right subtree.
• If you reach None: the value is not in the tree.

Example: search for 60

• At 50: 60 > 50 → go right to 70.
• At 70: 60 < 70 → go left to 60.
• At 60: 60 == 60 → found in 3 comparisons.

Example: search for 55

• At 50 → right to 70 → left to 60 → left — None. Not found in 4 comparisons.

How do you traverse a BST to get values in sorted order?

In-order traversal visits nodes in the order: left subtree → current node → right subtree. For a BST, this always produces the values in ascending sorted order — a key property.

Recursively:

in_order(node):
    if node is None: return
    in_order(node.left)
    print(node.value)
    in_order(node.right)

Applying in-order to the original tree (root=50):

Output: 20, 30, 40, 50, 60, 70, 80 — perfectly sorted.

What is the time complexity of BST operations?

In a balanced BST, each level roughly halves the remaining values, giving a height of log₂n. In an unbalanced BST — for example, if values are inserted in sorted order — the tree degenerates into a linked list and every operation must traverse all n nodes.

What makes a BST become unbalanced?

Inserting values in sorted order (e.g. 10, 20, 30, 40, 50) produces a "right-skewed" tree with no left branches:

10
  \
  20
    \
    30
      \
      40
        \
        50

Searching for 50 requires visiting all 5 nodes — O(n) — instead of the O(log n) you would get from a balanced tree. Self-balancing BSTs (such as AVL trees and Red-Black trees) automatically reorganise after each insertion to maintain balance, but these are beyond the GCSE specification.

Frequently asked questions

Why does in-order traversal produce a sorted list from a BST?

The BST ordering rule guarantees that every node in the left subtree is smaller and every node in the right subtree is larger. In-order traversal visits the entire left subtree (all smaller values) before the current node, then the entire right subtree (all larger values). Applying this rule recursively means the traversal naturally visits nodes from smallest to largest — the definition of ascending sorted order.

Can a BST contain duplicate values?

The standard BST definition requires all values to be unique. If duplicates must be stored, the convention is to treat "equal" values as going to the left (or right) consistently. Some implementations track a count per node rather than allowing duplicate nodes. At GCSE, assume values are unique unless a question states otherwise.

How does BST search compare with binary search on a sorted array?

Both achieve O(log n) for a balanced BST or a sorted array. The key difference is in insertion and deletion: inserting into a sorted array requires shifting elements — O(n) — while inserting into a balanced BST is O(log n). The BST is therefore preferred when the dataset changes frequently. A sorted array is preferred when the dataset is static and memory locality (cache performance) matters.

What is pre-order and post-order traversal?

• Pre-order visits the current node before its children: root → left → right. Useful for copying a tree or serialising its structure.
• Post-order visits the current node after its children: left → right → root. Useful for deleting a tree (children are deleted before parents) or evaluating expression trees.
• In-order (left → root → right) is the one that produces sorted output from a BST and is most commonly examined at GCSE.

---

For Socratic GCSE tutoring and free Computer Science flashcards, see aitutors.me.