IB COMPUTER SCIENCE | B4.1.4 Binary Search Trees (HL)

Lesson objective

Explain BST structure and ordering, sketch tree diagrams and trace insertion, search, traversal and deletion while relating performance to height.

Learn

B4.1.4 | BINARY SEARCH TREES (HL ONLY)

01 | A SEQUENCE IS NOT THE ONLY WAY TO ORGANISE DATA

A linked list gives each node a route to a next node. A binary search tree, or BST, organises keys into branching subtrees instead. At each node, a comparison helps decide which branch can contain the target.

Imagine a catalogue organised by numeric item ID. Starting from one root key, smaller keys belong in its left subtree and larger keys in its right subtree. Repeating that rule creates a searchable hierarchy.

A BST is not automatically balanced or always faster than a list. Its shape matters. We will build, sketch, search, traverse and delete nodes before evaluating that claim.

02 | LEARN THE TREE VOCABULARY

BST built from 50, 30, 70, 20, 40, 60, 80 20 30 40 50 60 70 80
BST built from 50, 30, 70, 20, 40, 60, 80. The root is pink; absent children are omitted.
Term Meaning in this tree
Root 50, the entry node with no parent
Parent and child 30 is a child of 50; 50 is its parent
Leaf 20, 40, 60 and 80 have no children
Subtree 30 together with its descendants 20 and 40
Path A connected route such as 50, 70, 60
Binary Each node has at most two children, labelled left and right

Binary does not mean every node must have exactly two children. A node may have zero, one or two. left and right are distinct positions, so draw a one-child node on the correct side.

03 | THE ORDERING RULE APPLIES TO ENTIRE SUBTREES

For the strict, unique-key BST used here, every key in a node’s left subtree is smaller than that node’s key, and every key in its right subtree is larger. The rule must hold recursively at every node.

Proposed placement Valid? Reason
40 as the right child of 30, inside 50’s left subtree Yes 40 is greater than 30 and less than 50
60 as the right child of 30, inside 50’s left subtree No 60 exceeds the ancestor bound 50
65 as the right child of 60, inside 70’s left subtree Yes 60 < 65 < 70

Checking only a child against its immediate parent is insufficient. The key also has to respect all relevant ancestor bounds. This global invariant is what makes branch elimination during search correct.

04 | DEFINE THE KEY AND DUPLICATE POLICY

A key is the value used for ordering and search. A node can also hold associated data, such as a catalogue record. For clarity, our implementations store only integer keys. The ordering comparisons must be meaningful and consistent for all permitted keys.

This lesson ignores duplicate insertions: insert returns False and leaves the tree unchanged when a key already exists. Other BST designs may store a count, group equal records, replace a mapped value or use a specified equal-key branch policy.

State the policy before sketching. Do not silently change it during insertion or deletion. A binary tree without the search-order invariant is not necessarily a BST.

05 | A NODE HAS LEFT AND RIGHT REFERENCES

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

None marks an absent child. The tree object holds root, which is None when empty. A leaf has both child references absent. Links describe structure, not a promise of adjacent physical memory.

A parent reference is optional metadata and is not stored in this implementation. Recursive deletion instead returns the new root of each affected subtree so the caller can reconnect it.

06 | INSERT BY FOLLOWING COMPARISONS

Insert 40 into a tree already containing 50 and 30 Decision
Compare with 50 40 < 50: move left
Compare with 30 40 > 30: move right
Right child of 30 is absent Attach a new node containing 40 there

Start at root. If the key is smaller, follow left; if larger, follow right. Attach the new node at the first absent child reached on that comparison path. If equality is found, follow the duplicate policy instead.

For an empty tree, the new node becomes root. A normal insertion does not sort all the existing keys again or move them into array positions. It adds one new leaf at the determined location.

07 | INSERTION ORDER CHANGES THE SHAPE

Increasing insertion order produces a right-skewed tree 20 30 40 50 60
Increasing insertion order produces a right-skewed tree. The root is pink; absent children are omitted.

The same set of keys can form different BST shapes depending on insertion order. Inserting sorted keys into this ordinary unbalanced BST produces a chain, because each new key is larger than all the earlier ones.

Compare with starting near the middle and distributing later keys across the two sides. Both results can satisfy the BST invariant, but they have different heights and search paths. This implementation performs no automatic rotations or rebalancing.

08 | SKETCH A BST IN A REPRODUCIBLE WAY

Write the insertion order above the diagram. Place the first key at the root, then add one key at a time by tracing comparisons. Leave enough horizontal space for both subtrees and draw links only to actual children.

For 50, 30, 70, 20, 40, 60, 80, place 50 first, then 30 left and 70 right. The remaining four keys attach at the next level. Check each key against ancestor bounds when you finish.

Do not draw a sorted row and arbitrarily join nearby values. The links should represent the comparison-based construction and the chosen insertion order.

09 | SEARCH CAN DISCARD AN ENTIRE BRANCH

Search for 65 in the main tree after inserting 65 Reason
50: move right 65 is larger, so the entire left subtree is excluded
70: move left 65 is smaller, so the right subtree is excluded
60: move right 65 is larger than 60
65: found Return success

An unsuccessful search ends when the required child is absent. For 99, visit 50, 70, 80 and then reach the absent right child. No other branch can contain it if the invariant is valid.

The number of visited nodes depends on the path length. A short tree can make that small, while a chain can require visiting all n nodes.

10 | INORDER TRAVERSAL: LEFT, NODE, RIGHT

A traversal visits every node according to a specified order. For inorder, first traverse the left subtree, then visit the current node, then traverse the right subtree. Apply that same rule recursively, not just once at root.

Main seven-node tree Order of visited keys
Inorder 20, 30, 40, 50, 60, 70, 80

The output is ascending under this unique-key BST invariant. The algorithm does not rearrange the nodes or run a separate sorting routine; the tree’s ordering property makes the visit order sorted.

An empty subtree contributes no values. A full traversal still visits all n nodes, so it takes O(n) time even when the tree is well shaped.

11 | PREORDER AND POSTORDER

Traversal Recursive rule Main seven-node output
Preorder Node, left, right 50, 30, 20, 40, 70, 60, 80
Postorder Left, right, node 20, 40, 30, 60, 80, 70, 50
Inorder Left, node, right 20, 30, 40, 50, 60, 70, 80

Visit means the action chosen for that traversal, such as recording the key. In preorder the action happens before the child calls; in postorder it happens after both child calls. The physical drawing can stay the same while the recorded sequence changes.

Postorder is useful when children must be processed before their parent. Preorder visits parents before descendants. Only inorder is guaranteed to produce sorted keys for this BST contract.

12 | FIND THE MINIMUM AND MAXIMUM

For a non-empty BST, the minimum key is reached by following left until there is no further left child. The maximum is reached by following right in the same way.

In the main tree, the minimum is 20 and the maximum is 80. In a subtree rooted at 70, its minimum is 60. That second idea becomes important when selecting an inorder successor for deletion.

The path takes O(h) time for height h under a standard model. An empty-tree minimum or maximum needs an explicit failure policy; there is no ordinary key to return.

13 | DELETE A LEAF: REPLACE ITS LINK WITH NONE

After deleting leaf 20 30 40 50 60 70 80
After deleting leaf 20. The root is pink; absent children are omitted.

A leaf has no children to preserve below it. To delete 20, locate it and change its parent’s left reference to None. The remaining keys stay in their correct ancestor ranges.

If the root is the only node, deleting that leaf makes root None. The root case is not handled by changing a nonexistent parent; the tree’s root reference itself must be updated.

Removing a node from the tree does not promise immediate memory reclamation if another reference still reaches that object.

14 | DELETE A NODE WITH ONE CHILD

After deleting 60, its right child 65 takes its subtree position 20 30 40 50 65 70 80
After deleting 60, its right child 65 takes its subtree position. The root is pink; absent children are omitted.

Node 60 has one child, 65. Reconnect 70.left directly to 65, replacing the subtree root 60 with its child. All the child’s descendants would come with that subtree; do not drop them.

This works because the child subtree already lies within the deleted node’s ancestor bounds. For root deletion with one child, root becomes that child. The code must update the incoming reference, not just clear the deleted key.

15 | TWO CHILDREN: CHOOSE AN ORDER-PRESERVING REPLACEMENT

When a node has two children, simply attaching one child in its place can lose or misplace the other subtree. Instead choose a replacement key that fits between the remaining left and right keys.

The inorder successor is the smallest key in the node’s right subtree. Go right once, then follow left as far as possible. The inorder predecessor, the largest key in the left subtree, is a valid alternative under a consistent deletion algorithm.

The successor has no left child by definition. It can still have a right child, which must be reconnected when the successor node is removed from its old position.

16 | TWO-CHILD DELETION WITH A SUCCESSOR CHILD

Before deleting 50: successor 60 has right child 65 20 30 40 50 60 65 70 80
Before deleting 50: successor 60 has right child 65. The root is pink; absent children are omitted.
Stage What changes
Find the successor From 50.right = 70, follow left to 60
Copy the successor key into the target position The root position now stores 60
Remove the original successor from the right subtree Reconnect 70.left to 65
Final invariant All remaining left keys are below 60 and right keys are above 60
Completed deletion of 50, with 65 preserved 20 30 40 60 65 70 80
Completed deletion of 50, with 65 preserved. The root is pink; absent children are omitted.

Our key-only implementation copies the successor key and removes its old node. There must not be two active copies of that key when the operation returns. If nodes store records as well as keys, move the associated record consistently rather than copying only its key.

Copying a key changes the key stored in the target node object; it does not move that object to a new memory address. Node handles and identity policies would need extra care in an API that exposes them.

17 | RETURN THE NEW SUBTREE ROOT

# Public operation:
def delete(self, key):
    self.root, removed = self._delete(self.root, key)
    return removed

The helper returns a pair: the new subtree root and whether a key was removed. Its caller assigns that returned reference back into root, left or right as appropriate.

A leaf replacement is None. A one-child replacement is that child. A two-child case keeps a target-position node after replacing its key and deleting the successor. Assigning the returned root is what makes root deletion and internal deletion follow the same structure.

18 | COMPLETE PYTHON BST

Save this as bst_demo.py. The implementation supports unique integer keys, iterative insertion and search, three traversals and deletion with a successor. It is an ordinary unbalanced BST with no parent fields.

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
            return True
        current = self.root
        while True:
            if key == current.key:
                return False
            if key < current.key:
                if current.left is None:
                    current.left = Node(key)
                    return True
                current = current.left
            else:
                if current.right is None:
                    current.right = Node(key)
                    return True
                current = current.right

    def contains(self, key):
        current = self.root
        while current is not None:
            if key == current.key:
                return True
            current = current.left if key < current.key else current.right
        return False

    def inorder(self):
        result = []
        def visit(node):
            if node is not None:
                visit(node.left)
                result.append(node.key)
                visit(node.right)
        visit(self.root)
        return result

    def preorder(self):
        result = []
        def visit(node):
            if node is not None:
                result.append(node.key)
                visit(node.left)
                visit(node.right)
        visit(self.root)
        return result

    def postorder(self):
        result = []
        def visit(node):
            if node is not None:
                visit(node.left)
                visit(node.right)
                result.append(node.key)
        visit(self.root)
        return result

    def delete(self, key):
        self.root, removed = self._delete(self.root, key)
        return removed

    def _delete(self, node, key):
        if node is None:
            return None, False
        if key < node.key:
            node.left, removed = self._delete(node.left, key)
            return node, removed
        if key > node.key:
            node.right, removed = self._delete(node.right, key)
            return node, removed
        if node.left is None:
            return node.right, True
        if node.right is None:
            return node.left, True
        successor = node.right
        while successor.left is not None:
            successor = successor.left
        node.key = successor.key
        node.right, _ = self._delete(node.right, successor.key)
        return node, True

Recursive traversal stores pending calls along the current path. Recursive deletion also uses the call stack. A very skewed large tree can exceed Python’s recursion limit; this teaching implementation is intended for modest examples, not guaranteed stack-safe processing of arbitrarily deep trees.

19 | RUN AND CHECK THE WORKED PROGRAM

tree = BST()
for key in (50, 30, 70, 20, 40, 60, 80):
    tree.insert(key)
print(tree.inorder())
print(tree.preorder())
print(tree.postorder())
print(tree.contains(60), tree.contains(99))
print(tree.insert(50))
tree.insert(65)
print(tree.delete(50))
print(tree.inorder())
print(tree.root.key)

The three traversal outputs match the seven-node sequences above. Membership prints True False; inserting duplicate 50 prints False. After adding 65, deleting 50 prints True. The inorder result is [20, 30, 40, 60, 65, 70, 80], and the root key is 60.

The tree has lost exactly the requested key 50. The successor key 60 remains once, and its former right child 65 is still present. These are important checks for a two-child deletion.

20 | INTERACTIVE BST EXPLORER

Choose insertion, successful or unsuccessful search, one of the three deletion cases, or a traversal. Each task resets to its own stated tree. Predict the comparison or returned sequence before stepping. The final mutation is performed by the actual BST implementation.

A highlighted node is the current comparison or visit. Deletion tasks first identify the target and replacement, then show the completed reconnection without presenting a half-finished tree as a valid final state.

21 | COMPLETE JAVA BST

Save this as BSTExample.java and run main. It implements the same unique integer-key ordering and successor deletion. The membership checks are printed on separate lines in this Java caller.

import java.util.ArrayList;
import java.util.List;

class Node {
    int key;
    Node left, right;
    Node(int key) { this.key = key; }
}
class BST {
    private Node root;
    public boolean insert(int key) {
        if (root == null) {
            root = new Node(key);
            return true;
        }
        Node current = root;
        while (true) {
            if (key == current.key) return false;
            if (key < current.key) {
                if (current.left == null) {
                    current.left = new Node(key);
                    return true;
                }
                current = current.left;
            } else {
                if (current.right == null) {
                    current.right = new Node(key);
                    return true;
                }
                current = current.right;
            }
        }
    }
    public boolean contains(int key) {
        Node current = root;
        while (current != null) {
            if (key == current.key) return true;
            current = key < current.key ? current.left : current.right;
        }
        return false;
    }
    public List<Integer> inorder() {
        List<Integer> result = new ArrayList<>();
        inorder(root, result);
        return result;
    }
    private void inorder(Node n, List<Integer> result) {
        if (n == null) return;
        inorder(n.left, result);
        result.add(n.key);
        inorder(n.right, result);
    }
    public List<Integer> preorder() {
        List<Integer> result = new ArrayList<>();
        preorder(root, result);
        return result;
    }
    private void preorder(Node n, List<Integer> result) {
        if (n == null) return;
        result.add(n.key);
        preorder(n.left, result);
        preorder(n.right, result);
    }
    public List<Integer> postorder() {
        List<Integer> result = new ArrayList<>();
        postorder(root, result);
        return result;
    }
    private void postorder(Node n, List<Integer> result) {
        if (n == null) return;
        postorder(n.left, result);
        postorder(n.right, result);
        result.add(n.key);
    }
    public boolean delete(int key) {
        if (!contains(key)) return false;
        root = remove(root, key);
        return true;
    }
    private Node remove(Node n, int key) {
        if (n == null) return null;
        if (key < n.key) n.left = remove(n.left, key);
        else if (key > n.key) n.right = remove(n.right, key);
        else {
            if (n.left == null) return n.right;
            if (n.right == null) return n.left;
            Node successor = n.right;
            while (successor.left != null) successor = successor.left;
            n.key = successor.key;
            n.right = remove(n.right, successor.key);
        }
        return n;
    }
}
public class BSTExample {
    public static void main(String[] args) {
        BST tree = new BST();
        int[] keys = {50, 30, 70, 20, 40, 60, 80};
        for (int key : keys) tree.insert(key);
        System.out.println(tree.inorder());
        System.out.println(tree.preorder());
        System.out.println(tree.postorder());
        System.out.println(tree.contains(60));
        System.out.println(tree.contains(99));
        System.out.println(tree.insert(50));
        tree.insert(65);
        System.out.println(tree.delete(50));
        System.out.println(tree.inorder());
    }
}

For clarity, Java delete first checks membership, then performs removal. That adds a search pass but remains O(h) time in the standard model. The helper still returns the replacement subtree root, so the root field and child references can be updated correctly.

The Java code is also unbalanced and uses recursive traversal and removal. It has the same conceptual deep-tree stack concern, subject to its runtime’s stack resources.

22 | HEIGHT CONTROLS THE SEARCH PATH

In this lesson, height counts edges on the longest downward path. A one-node tree has height 0, and the main seven-node tree has height 2. An empty tree can be assigned height −1 under this convention. Other materials count levels, so state the convention.

Shape for n nodes Height growth Search, insertion and deletion
Well-balanced shape O(log n) O(log n) paths under the standard model
A chain O(n) O(n) worst case
Any shape: full traversal May vary O(n) visits regardless of balance

A successful search can visit up to h + 1 nodes. Ordinary BST insertion does not guarantee logarithmic height. Balanced tree variants maintain additional rules and may perform rotations; those mechanisms are not part of this implementation.

23 | TIME, SPACE AND ORGANISATION

A BST supports key lookup and ordered traversal in one representation. Unlike an array index, the key comparisons route the search. Unlike a hash-based set, the tree’s ordering can support minimum/maximum and ordered or bounded-range processing.

Each node stores child references and key data, so structural storage is O(n). Our iterative contains uses O(1) auxiliary state. Recursive traversals and deletion can retain O(h) stack frames; the returned traversal lists also use O(n) output space.

A range query can exploit ordering in a suitable implementation, but the simple code here exposes only full traversal. Do not claim a capability or efficiency that the actual method does not provide.

24 | TEST THE INVARIANT, NOT ONLY ONE OUTPUT

tree = BST()
for key in (50, 30, 70, 20, 40, 60, 80, 65):
    assert tree.insert(key)
assert tree.insert(60) is False
assert tree.delete(50) is True
assert tree.inorder() == [20, 30, 40, 60, 65, 70, 80]
assert tree.contains(50) is False
assert tree.contains(65) is True
assert tree.delete(99) is False

Run these assertions with BST defined. Also test empty search and deletion, deleting the only root, a root with one child, leaf removal and a successor that is the immediate right child. Keep expected key membership independent of the tree implementation.

To validate structure directly, carry lower and upper bounds down the tree. Every key must lie strictly between its inherited bounds. This catches violations that checking only parent-child pairs would miss.

25 | COMMON MISTAKES AND HOW TO EXPLAIN THEM

Mistake Repair
Check only an immediate parent Apply the invariant to the entire subtree and ancestor bounds
Assume every BST is balanced Use insertion order and height to evaluate paths
Forget to update root after deletion Assign the returned subtree root
Delete the successor’s right child as well Reconnect that child when removing the original successor
Copy a successor key but leave its original active Complete removal so the unique-key policy holds
Confuse traversal order with tree shape Trace the exact visit rule on the same structure

Explain a search with comparison, selected branch and excluded subtree. Explain deletion with the incoming reference, retained child subtree and preserved ordering. Connect those steps with because or therefore to make the reasoning visible.

26 | SKETCH, TRACE AND JUSTIFY

Construct a tree from 45, 25, 65, 15, 35, 55, 75, 60. Sketch every child on the correct side. Write the search path for 60, then give inorder, preorder and postorder sequences before running any code.

Delete 15, then 55, then 45 in that order. Identify which deletion case applies each time, preserve all remaining keys and justify the successor choice. Compare the height with a tree built by inserting the same keys in increasing order.

The next lesson constructs sets as an ADT. Keep the difference between a logical membership contract and a particular ordered-tree implementation in mind.

MATCH THE BST IDEA

Terminology

Terminology

Binary search tree

A binary tree satisfying a specified search-order invariant at every node.

Root

The entry node with no parent.

Parent

The node directly above a child through a tree link.

Child

A node connected immediately below a parent.

Leaf

A node with no children.

Subtree

A node and all descendants reachable below it.

Key

The value used for ordering and comparison.

BST invariant

In this strict policy, all left-subtree keys are smaller and all right-subtree keys larger than the node’s key.

Binary tree

A tree with at most two children per node, with distinct left and right positions.

Ancestor bound

A key restriction inherited from a higher node on the path.

Search path

The comparison-selected route followed while locating a key.

Insertion order

The sequence of keys added, which can determine an unbalanced BST’s shape.

Duplicate policy

The specified treatment of an already-present key.

Inorder traversal

Visit left subtree, node, then right subtree.

Preorder traversal

Visit node, left subtree, then right subtree.

Postorder traversal

Visit left subtree, right subtree, then node.

Inorder successor

The next larger key; for a node with a right subtree, its right-subtree minimum.

Inorder predecessor

The next smaller key; for a node with a left subtree, its left-subtree maximum.

Leaf deletion

Replace the removed leaf’s incoming route with an absent reference.

One-child deletion

Replace the removed node’s incoming route with its child subtree.

Two-child deletion

Use an order-preserving replacement and remove it from its former position.

Subtree root return

A helper returns the node that should become the root of the modified subtree.

Height

Here, the number of edges on the longest downward path.

Balanced shape

A shape with sufficiently controlled subtree heights for short paths; the exact rule depends on the tree variant.

Skewed tree

A tree whose nodes mainly form a one-sided chain.

Unbalanced BST

A BST without an automatic height-control mechanism.

Recursive traversal

A visit procedure applying the same rule to child subtrees.

Auxiliary stack space

Memory for pending recursive calls, separate from stored nodes and output.

Ordered traversal

Visiting keys according to their defined order, such as BST inorder.

Structural validation

Checking links and inherited ordering bounds rather than only one observed output.

Questions

Questions

CHECK YOUR UNDERSTANDING

Select all correct choices. Each exact set earns one point.

1. Which statements describe the strict BST invariant here?
2. Which binary-tree statements are correct?
3. For inserting 40 after 50 and 30, which path is correct?
4. Which apply to the main tree’s inorder traversal?
5. Which deletion rules are correct?
6. For deleting 50 in the eight-node example, which are true?
7. Which describe a successor chosen from the right subtree?
8. Which performance statements are accurate?
9. Which tests are useful?
10. Which match the chosen implementation?

EXPLAIN AND COMPARE

Write your answers before revealing each sample.

1. Define a binary search tree under this lesson’s key policy.

2. Explain why a node 60 under the right of 30 can still violate a root 50 BST.

3. Construct the BST for 50, 30, 70, 20, 40, 60, 80.

4. Trace the search for 65 after adding it to the main tree.

5. Distinguish inorder, preorder and postorder.

6. Explain leaf and one-child deletion.

7. Explain deletion of 50 when successor 60 has right child 65.

8. Explain why a deletion helper returns a subtree root.

9. Evaluate the claim that a BST always searches faster than a linked list.

10. Describe this lesson’s height convention and complexity consequences.

11. Construct a test plan for BST deletion.

12. Explain why copying only the key can be wrong for record-bearing nodes.

CONSTRUCT AND TRACE | THREE DELETION CASES

Construct a BST from 45, 25, 65, 15, 35, 55, 75, 60. Trace a search for 60. Then delete 15, 55 and 45 in that order, explaining the three deletion cases.

Reveal a worked check
tree = BST()
for key in (45, 25, 65, 15, 35, 55, 75, 60):
    tree.insert(key)
assert tree.contains(60)
for key in (15, 55, 45):
    assert tree.delete(key)
assert tree.inorder() == [25, 35, 60, 65, 75]
assert tree.root.key == 60

The search path is 45, 65, 55, 60. First remove leaf 15. Then replace one-child 55 with 60. Finally delete two-child root 45 using successor 60, removing its old occurrence from the right subtree. The remaining root is 60, with 25 and 65 as children, 35 to the right of 25, and 75 to the right of 65.

Flashcards

Flashcards

Click to flip. Select the ideas you need to revisit.

0 cards selected for revision.

Selections are kept while this page is open.

Workbook

Workbook

COMING SOON

The workbook for B4.1.4 Binary Search Trees (HL) is coming soon. Complete the matching task and written questions in your exercise book.