Binary search trees: structure and insertion
Sketch, search and insert in a BST while preserving its ordering property.
Every comparison chooses one subtree
- explain how BSTs organize data;
- sketch a BST from an insertion sequence;
- trace search and insertion decisions;
- explain why recursion maps naturally to subtree operations.
Rapid Recall Deck
Attempt each card first. If a term is new, flip and study it, then answer it again without looking. Mark only secure recall as “Know it”.
The ordering rule prunes impossible branches
50
/ \
30 70
/ \ / \
20 40 60 80Search path
Trace the comparisons made when searching for 60.
Compare 60 with 50: go right. Compare 60 with 70: go left. Compare with 60: found. Path: 50 → 70 → 60.
Missing value
Trace the search for 65 and state when the algorithm knows it is absent.
50 → right to 70 → left to 60 → right. The right child of 60 is empty, so the only valid path for 65 has ended and the value is absent.
Insertion order determines the shape
Sketch from insertion order
Starting from an empty BST, insert these values in order: 50, 30, 70, 20, 40, 60, 80, 65. Sketch the final tree.
50
/ \
30 70
/ \ / \
20 40 60 80
\
65A subtree is a smaller instance of the same structure
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return TreeNode(value)
if value < root.value:
root.left = insert(root.left, value)
elif value > root.value:
root.right = insert(root.right, value)
return rootExplain why this insertion is recursive
After comparing the new value with a node, insertion becomes the same problem on either the left or right subtree. The base case occurs when that subtree root is None, where the new node is created. Each recursive call returns the updated subtree root so the parent keeps the correct child reference.
BST ordering works with comparable keys
Balanced shape
Consider this BST: 50. Explain why this reasonably balanced shape can search faster than a chain-shaped BST containing the same seven values.
├─ 30
│ ├─ 20
│ └─ 40
└─ 70
├─ 60
└─ 80
A reasonably balanced tree reduces the remaining candidate set through branching, so the path height stays much smaller. A chain-shaped BST may require visiting nearly every node, behaving like a linear structure.
Ordering with strings
A BST stores names using normal lexicographic string comparison. Starting with root "Maya", where would "Ari" and "Zoe" be inserted relative to the root?
"Ari" is less than "Maya", so it goes left. "Zoe" is greater, so it goes right.
Practice the exact sketching skill seen in the specimen
Paper 2-style sketch
The current BST is:
Martin
/ \
Jeanne Pedro
/ \
Hwang Manuel
Using lexicographic comparison, insert Louis and then Indie. Sketch only the final tree.
Martin
/ \
Jeanne Pedro
/ \
Hwang Manuel
\ /
Indie LouisLouis follows Martin → Jeanne → Manuel → left. Indie follows Martin → Jeanne → Hwang → right.
Use the invariant, not guesswork
Exit explanation
Why does a BST search not normally need to inspect both children after comparing the target with a node?
The ordering property tells which side could contain the target. If the target is smaller, every larger/right-side path can be rejected; if larger, the left side can be rejected.
Finish the learning cycle
IA — main task
Continue Criterion D implementation/testing and document one implementation choice with evidence of why it works.
Paper 2 — short practice
Sketch BSTs for two different insertion orders using the same values, then explain why their shapes — and search performance — can differ.