BST operations, traversal and evaluation
Explain traversal and deletion while maintaining the BST property, then reason about balanced versus skewed performance.
Deleting a node must preserve the ordering invariant
- trace inorder, preorder and postorder traversal in a binary search tree;
- explain BST deletion for leaf, one-child and two-child cases;
- search and sketch after updates;
- explain how tree shape affects performance and data organization.
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 visit position defines the traversal
50
/ \
30 70
/ \ / \
20 40 60 80Inorder
Write the traversal output.
20, 30, 40, 50, 60, 70, 80.
Preorder
Write the traversal output.
50, 30, 20, 40, 70, 60, 80.
Postorder
Write the traversal output.
20, 40, 30, 60, 80, 70, 50.
Three cases, one invariant
Case 1 · leaf
Using this BST: 50, delete leaf node
├─ 30
│ ├─ 20
│ └─ 40
└─ 70
├─ 60
└─ 8020. Which parent reference changes, and what should it become?
Set 30’s left child reference to None. No subtree needs to be preserved below 20.
Case 2 · one child
Suppose node 60 has one right child 65. If 60 is deleted, what should 70’s left reference become?
It should reference 65 directly, bypassing the removed 60 node while preserving the subtree.
Case 3 · two children
If 50 is deleted, name one valid replacement strategy.
Replace 50 with its inorder successor (the smallest value in the right subtree, 60) or its inorder predecessor (the largest value in the left subtree, 40), then remove that replacement node from its old position.
Deletion must still leave a valid BST
Sketch after deletion
Using this BST: 50, delete
├─ 30
│ ├─ 20
│ └─ 40
└─ 70
├─ 60
└─ 8050 by replacing it with its inorder successor. Sketch the final BST.
60
/ \
30 70
/ \ \
20 40 8060 replaces 50, and the original 60 node is removed from the left side of 70.
Tree shape changes practical performance
Explain inorder
Why does inorder traversal of a standard BST produce values in ascending order?
The traversal processes every smaller left-subtree value before the node and every larger right-subtree value after the node. Applying that rule recursively preserves ascending order throughout the tree.
Explain performance risk
Insert 10, 20, 30, 40, 50 into an empty BST in that order. What shape results, and why is that undesirable for searching?
The tree becomes a right-skewed chain. Searching may need to visit nearly every node, so the branching advantage of a balanced BST is lost.
Explain structure and consequences clearly
Teacher-created Paper 2 mini-set
1. Explain how a BST organizes keys to support searching.
2. For this BST—50—state the inorder traversal.
├─ 30
│ ├─ 20
│ └─ 40
└─ 70
├─ 60
└─ 80
3. Explain how to delete a BST node with two children.
4. Explain why a highly skewed BST can perform poorly.
- Smaller keys are placed in the left subtree and larger keys in the right, so one branch is chosen from each comparison.
- 20, 30, 40, 50, 60, 70, 80.
- Use an inorder successor/predecessor as a replacement, then remove that node from its original position while reconnecting any remaining child.
- Long one-sided paths can make search/insert approach linear traversal instead of benefiting from a shallow branching structure.
Deletion is constrained by ordering
Exit check
Why is “replace a two-child node with any value from its right subtree” incorrect?
An arbitrary right-subtree value may break ordering relative to other nodes. A standard safe replacement is the smallest value in the right subtree (inorder successor), or equivalently the largest value in the left subtree.
Finish the learning cycle
IA — main task
Continue Criterion D implementation/testing and add evidence for a test that changed program state, not only a normal happy-path input.
Paper 2 — short practice
From memory, produce all three traversals for one BST and sketch one deletion example for each of the three deletion cases.