Binary Search Tree (BST) — BST property, insert, search, delete (3 cases): Worked examples

Before any code, one reminder of the terms and one convention we use everywhere:

The scenario matrix

Every problem in BST-land falls into one of these cells. Our examples below are labelled with the cell they cover, and together they hit all of them.

#	Cell (scenario class)	What makes it special	Covered by
A	Search — key present	falls onto a node	Ex 1
B	Search — key absent	"falls off" to `None`	Ex 1
C	Insert — normal build	new keys become leaves	Ex 2
D	Insert — degenerate (sorted input)	tree becomes a stick, height $n - 1$	Ex 3
E	Insert — duplicate key	must be ignored / not double-added	Ex 2
F	Delete — Case 1 (leaf)	0 children	Ex 4
G	Delete — Case 2 (one child)	splice the single child up	Ex 5
H	Delete — Case 3 (two children)	replace with in-order successor	Ex 6
I	Delete — Case 3 where successor has a right child	successor is not a leaf	Ex 7
J	Degenerate / empty tree edge inputs	`None` root, delete-missing key	Ex 8
K	Validation — sneaky invalid tree	passes local check, fails global	Ex 9
L	Word problem (real-world)	model a scenario as a BST	Ex 10
M	Exam twist — reconstruct from traversals	reason backwards	Ex 11

We will use one shared tree for many examples so you can watch it change. Here it is:

Figure — Binary Search Tree (BST) — BST property, insert, search, delete (3 cases)

In-order walk of this tree: $20, 30, 40, 50, 60, 70$ — sorted ✓, so it is a valid BST.

Example 1 — Search, present (Cell A) and absent (Cell B)

Worked example Search for target

$t = 40$ , then for target $t = 45$ , in the shared tree. Forecast: Guess how many comparisons each search needs before reading on.

Searching for $t = 40$ (recall: $t$ is the target key we defined above):

Start at root $50$ . Compare $40 < 50$ → go left. Why this step? The invariant says everything $\geq 50$ lives to the right; $40 < 50$ so it cannot be there — we throw away the whole right subtree in one comparison.
At $30$ : $40 > 30$ → go right. Why this step? Everything left of $30$ is $< 30$ , but $40 > 30$ , so the answer can only be on the right.
At $40$ : $40 = 40$ → found (we touched 3 nodes, so 3 comparisons).

Searching for $t = 45$ :

At $50$ : $45 < 50$ → left.
At $30$ : $45 > 30$ → right.
At $40$ : $45 > 40$ → right. But $40$ has no right child → we hit None.
None reached → not present (Cell B). Why this step? "Falling off" to None means $45$ would have belonged exactly there. Its absence proves it isn't in the tree.

Verify: Both searches followed a single root-to-leaf path. We ended at node $40$ , whose depth is $2$ (edges $50 - 30$ and $30 - 40$ ), so comparisons $= depth + 1 = 3$ for $40$ ; the failed $45$ also touched 3 nodes then None. The tree's height is $h = 2$ edges, and the cost is $O (h)$ — comparisons grow with height, not exceeding $h + 1$ . ✓

Example 2 — Building a tree; duplicate ignored (Cells C, E)

Worked example Insert into an empty BST, in order:

$50, 30, 70, 20, 40, 60$ , then insert $30$ again. Forecast: Where does the second $30$ end up?

$50$ → becomes root (tree was empty). Why? First key has nothing to compare against.
$30 < 50$ → left child of $50$ .
$70 > 50$ → right child of $50$ .
$20 < 50$ → left; $20 < 30$ → left child of $30$ .
$40 < 50$ → left; $40 > 30$ → right child of $30$ .
$60 > 50$ → right; $60 < 70$ → left child of $70$ . Why each step? We descend exactly like a search; the first empty (None) slot we reach is the key's sorted position, so it becomes a new leaf, breaking nothing.
Insert $30$ again: at $50$ , $30 < 50$ → left; at $30$ , $30 == 30$ → duplicate, ignore. Why this step? Our insert has no branch for v == key, so it just falls through and returns. The tree is unchanged.

Verify: In-order walk = $20, 30, 40, 50, 60, 70$ (six keys, one $30$ ). Sorted ✓, no duplicate appeared. This is exactly the shared tree in figure s01.

Example 3 — Degenerate insert: the stick (Cell D)

$10$ → root.

$20 > 10$ → right child of $10$ .

$30 > 10$ → right; $30 > 20$ → right child of $20$ .

$40 > 10$ → right; $40 > 20$ → right; $40 > 30$ → right child of $30$ . Why this happens? Every new key is larger than all existing keys, so it always turns right, forever. There is never a left branch to balance things.

Result: a right-leaning "stick" of height $h = n - 1 = 3$ edges.

Verify: Searching for $40$ now touches all 4 nodes → 4 comparisons — as slow as scanning a linked list, $O (n)$ not $O (lo g n)$ . Same set of keys, worst order. This is exactly why AVL Tree and Red-Black Tree self-balance. In-order walk = $10, 20, 30, 40$ ✓ (still a valid BST — just a bad-shaped one). See Tree Height vs Depth.

Example 4 — Delete a leaf (Cell F, Case 1)

Example 5 — Delete a one-child node (Cell G, Case 2)

Example 6 — Delete a two-child node, successor is a leaf (Cell H, Case 3)

Search finds $50$ = root, with two children → Case 3.

Find the in-order successor = find_min(right subtree) = leftmost node of the subtree rooted at $70$ . Walk: $70$ has left child $60$ ; $60$ has no left child → successor $= 60$ . Why the successor? We need a replacement that is bigger than everything on the left (so the left subtree stays valid) and smaller than everything else on the right. The smallest key in the right subtree is exactly that borderline value.

Copy $60$ 's key into the root: root's key becomes $60$ . Why copy, not move pointers? Copying the key is cheaper and keeps all subtree links intact; we only need to erase the duplicate left behind.

Delete $60$ from the right subtree. $60$ is a leaf → Case 1, just remove it. Why is this always easy? The leftmost node has no left child by definition, so deleting the successor is always Case 1 or 2 — never another Case 3. The recursion cannot loop.

Verify: New in-order walk = $20, 30, 40, 60, 70$ . Sorted ✓. Root is now $60$ , left subtree ( $20, 30, 40$ ) all $< 60$ , right ( $70$ ) $> 60$ . Invariant holds. ✓

Example 7 — Case 3 where the successor has a right child (Cell I)

Worked example Build this tree and delete

$50$ :

Forecast: The successor of $50$ is $55$ — but $55$ has a right child $60$ . Does that break the "successor is a leaf" comfort we had in Example 6?

$50$ has two children → Case 3.
Successor = leftmost of right subtree ( $70$ 's subtree): $70$ has left child $55$ ; $55$ has no left child → successor $= 55$ .
Copy $55$ up: root key becomes $55$ .
Delete $55$ from the right subtree. Here $55$ has left = None but right = 60 → one child, Case 2. Splice $60$ up so it becomes $70$ 's left child. Why this step? The successor is guaranteed to have no left child (it's the leftmost node), but it may have a right child. That still keeps deletion in Case 1 or Case 2 — never Case 3. Everything stays finite.

Verify: New in-order walk = $30, 55, 60, 70$ . Sorted ✓. Root $55$ : left ( $30$ ) $< 55$ , right subtree keys ( $60, 70$ ) $> 55$ . Invariant holds. This is the general Case 3 — Example 6 was just the lucky leaf sub-case. ✓

Example 8 — Empty tree and deleting a missing key (Cell J)

Worked example (a) Search

$99$ in an empty tree. (b) Delete $99$ from the shared tree (no such key). Forecast: What should each return, and should anything crash?

(a) Empty tree:

search(None, 99): the while node is not None loop body never runs → returns None. Why? No root means no comparisons possible; "not found" is the only honest answer.

(b) Delete missing key $99$ :

At $50$ : $99 > 50$ → recurse right into $70$ .
At $70$ : $99 > 70$ → recurse right. $70$ 's right child is None.
delete(None, 99) → the base case if root is None: return None fires. Why this step? Reaching None means the key was never in the tree; we return None back up and every parent pointer is reassigned to its unchanged value — a harmless no-op.

Verify: The tree is unchanged; in-order walk still $20, 30, 40, 50, 60, 70$ ✓. No exception thrown. Degenerate inputs handled cleanly. ✓

Example 9 — The sneaky invalid tree (Cell K, validation)

Worked example Is this a valid BST?

Forecast: Every node's immediate children obey left < node < right. So it must be valid... right?

Local child checks all pass: $5 < 10 < 15$ ✓, and $6 < 15$ ✓.
But $6$ sits in the right subtree of $10$ , and everything there must be $> 10$ . Yet $6 < 10$ . Invalid. Why the local check fails? The BST property is recursive over ancestors, not just parents. A node inherits a legal range $(l o w, hi g h)$ from the whole path above it.
Range validation: root $10$ allowed in $(- \infty, \infty)$ ✓. Right child $15$ allowed in $(10, \infty)$ ✓. Node $6$ is in $15$ 's left subtree, allowed in $(10, 15)$ . Check $10 < 6 < 15$ ? $10 < 6$ is false → reject.

Verify: In-order walk = $5, 10, 6, 15$ . Not sorted ( $10$ then $6$ ) → confirms invalid ✓. The lie-detector agrees with the range check.

Example 10 — Word problem (Cell L)

Worked example A leaderboard stores player scores. Scores arrive in this order:

$500, 800, 300, 650, 900$ . Build a BST keyed on score, then a new score $700$ arrives — where does it attach, and who is the next-higher score above $650$ ? Forecast: Guess the parent of $700$ and the successor of $650$ before computing.

Build: $500$ root; $800 > 500$ right; $300 < 500$ left; $650 > 500$ right, $650 < 800$ left of $800$ ; $900 > 500$ right, $900 > 800$ right of $800$ .
Insert $700$ : $700 > 500$ right; $700 < 800$ left; at $650$ , $700 > 650$ right. $650$ 's right is None → $700$ becomes right child of $650$ (a new leaf). Why here? $700$ slots between $650$ and $800$ in sorted order, and $650$ is the deepest node whose comparison still points toward that gap.
"Next-higher than $650$ " = in-order successor of $650$ . After inserting $700$ , $650$ now has a right child $700$ ; the leftmost of that right subtree is $700$ itself → successor $= 700$ . Why the successor answers this? "Smallest score strictly greater" is precisely the definition of in-order successor — a natural leaderboard query.

Verify: In-order walk = $300, 500, 650, 700, 800, 900$ . Sorted ✓. $700$ appears right after $650$ ✓, confirming both the attach point and the successor. This mirrors Binary Search on Sorted Array but supports live inserts.

Example 11 — Exam twist: rebuild from traversals (Cell M)

Worked example You are told a BST's

in-order walk is $10, 20, 30, 40, 50$ and its pre-order walk (node, then left, then right) is $30, 20, 10, 40, 50$ . Reconstruct the tree. Forecast: In a BST, in-order is always just the sorted keys — so the real information hides in pre-order. Which key is the root?

Pre-order visits the root first, so the root is the first pre-order key: $30$ . Why this step? Pre-order = node, then left, then right — the very first key printed is the whole tree's root.
Split the in-order list at $30$ : keys before it ${10, 20}$ = left subtree; keys after it ${40, 50}$ = right subtree. Why this step? In an in-order walk everything printed before the root is exactly its left subtree (all smaller keys), and everything after is the right subtree (all larger) — the BST property guarantees this clean split.
Recurse into the left subtree ${10, 20}$ . The next unused pre-order key is $20$ → it is this subtree's root. Split ${10, 20}$ at $20$ : ${10}$ before, nothing after → $10$ is $20$ 's left child. Why this step? Pre-order finishes the whole left subtree before touching the right, so its next key is always the left subtree's root; the in-order split then places the remaining key.
Recurse into the right subtree ${40, 50}$ . The next unused pre-order key is $40$ → this subtree's root. Split ${40, 50}$ at $40$ : nothing before, ${50}$ after → $50$ is $40$ 's right child. Why this step? Same rule applied to the right side; $50$ being after $40$ in in-order forces it to the right.

Resulting tree:

       30
      /  \
     20   40
    /       \
   10        50

Verify: Read the reconstructed tree's traversals back. Pre-order (node, left, right) = $30, 20, 10, 40, 50$ ✓ matches the given. In-order (left, node, right) = $10, 20, 30, 40, 50$ ✓ matches the given. Both agree, so the reconstruction is the unique correct tree. ✓

Wrap-up flow

Recall Self-test before moving on

Which delete case fires when you remove a node whose left child is None but right child exists? ::: Case 2 (one child) — root.left is None is true, so we return root.right. Why can Case 3's successor-deletion never itself be another Case 3? ::: The successor is the leftmost node of the right subtree, so it has no left child — at most one child, hence Case 1 or 2. In a valid BST, why does knowing the in-order walk give you no shape information? ::: In-order of any BST is always the sorted keys, identical for every shape holding that key set. If a search ends at a node of depth $d$ , how many comparisons did it make? ::: $d + 1$ — one per node touched along a path of $d$ edges. What structure fixes the degenerate stick from Example 3? ::: A self-balancing BST such as AVL Tree or Red-Black Tree.

Back to the parent BST note. Related contrasts: Heap vs BST, Binary Tree — terminology & traversals.