To insert into a binary search tree (BST), compare the new key with each node and follow the appropriate subtree until reaching an empty position. To delete, handle the node according to its number of children; to traverse, visit every node in a defined order.
The Reasoning and Mechanism
A BST maintains the BST property: every key in a node's left subtree is smaller than the node's key, while every key in its right subtree is larger. A consistent rule must be defined if duplicate keys are permitted.
For insertion:
- Begin at the root.
- If the new key is smaller, move left; if larger, move right.
- Repeat until the required child reference is empty.
- Create the new leaf node there.
For example, inserting 35 into a tree with root 50 and left child 30 first moves left from 50, then right from 30.
Deletion has three cases:
| Node condition | Deletion operation |
|---|---|
| No children | Remove the leaf by setting its parent's reference to null. |
| One child | Replace the node with its only child. |
| Two children | Replace its value with its in-order successor (smallest value in the right subtree) or in-order predecessor, then delete that replacement node from its original position. |
A tree traversal processes every node:
| Traversal | Visiting order and use |
|---|---|
| In-order | Left, root, right; produces keys in ascending order. |
| Pre-order | Root, left, right; useful for copying or serializing a tree. |
| Post-order | Left, right, root; useful when deleting an entire tree. |
Insertion, search, and deletion take average time in a reasonably balanced BST, but worst-case time is for a skewed tree. Every complete traversal takes .
Exam Technique
For an IB trace question, redraw the tree after every operation and verify the BST property. A common misconception is that deleting a node with two children means deleting its whole subtree; instead, replace its value with a valid successor or predecessor and then remove that node correctly.
