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
| 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
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
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
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
| 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 |
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.