Source: UIUC Data Structures
Tags: BST, binary search tree, insertion, deletion, IOP, IOS, in-order predecessor, in-order successor, comparisons, node removal
Difficulty: Intermediate Prerequisites: Basic tree terminology (root, leaf, child, parent, height), linked list deletion.
Big picture
Binary search trees are the backbone of efficient searching and sorting in memory. Every node enforces a simple rule: everything in the left subtree is smaller, everything in the right is larger. This structure lets you find, insert, and remove values in O(h) time, where h is the tree's height. The catch is that h depends on insertion order, so the same set of keys can produce a balanced tree or a skinny chain. This set of notes covers how insertion and deletion work mechanically, and what that costs.
Inserting into a BST always places the new node as a leaf; the number of comparisons equals the depth of that leaf position (best case 1, worst case n). Deletion has three cases depending on how many children the target node has: zero children (just remove it), one child (splice it out like a linked list node), or two children (swap with the in-order predecessor or successor, then remove the swapped node).
Binary search tree (BST)
A binary tree where, for every node, all keys in its left subtree are strictly less than the node's key, and all keys in its right subtree are strictly greater. In simple terms, left is smaller, right is bigger, all the way down.
Height of a tree
The length of the longest path from the root to a leaf, measured in edges. A single-node tree has height 0. In simple terms, it is how many steps it takes to reach the deepest leaf.
In-order predecessor (IOP)
The node with the largest key that is still smaller than a given node's key. Found by going left once, then right as far as possible. Think of it as the node that would appear immediately before the target if you printed the tree in sorted order.
In-order successor (IOS)
The node with the smallest key that is still larger than a given node's key. Found by going right once, then left as far as possible. Think of it as the node that would appear immediately after the target in sorted order.
When you insert a new node into a BST, you walk from the root down to a NULL position, comparing at each level.
Best case (minimum comparisons): 1 comparison. The tree is empty, so the new node becomes the root with zero traversal, or the tree has one node and you compare once.
Worst case (maximum comparisons): n comparisons, where n is the number of nodes already in the tree. This happens when the tree is a straight chain (every node has only one child), so you walk through every existing node before reaching the NULL at the bottom. The new node requires n + 1 comparisons if you count the final NULL check, or n if you count only node-to-node comparisons.
The number of comparisons for any single insertion equals the depth of the position where the new node lands, plus one.
The first value inserted always becomes the root. Each subsequent value is compared against existing nodes starting at the root, going left if smaller, right if larger, until a NULL child is found.
Example 1: Insert 4, 5, 6, 7, 1, 2, 3
4 becomes root.
5 > 4, goes right of 4.
6 > 4, 6 > 5, goes right of 5.
7 > 4, 7 > 5, 7 > 6, goes right of 6.
1 < 4, goes left of 4.
2 < 4, 2 > 1, goes right of 1.
3 < 4, 3 > 1, 3 > 2, goes right of 2.
Result: height = 3, with longest paths 4 → 1 → 2 → 3 and 4 → 5 → 6 → 7.
Example 2: Insert 5, 4, 7, 9, 8, 3, 1
5 is root.
4 < 5, left child of 5.
7 > 5, right child of 5.
9 > 5, 9 > 7, right child of 7.
8 > 5, 8 > 7, 8 < 9, left child of 9.
3 < 5, 3 < 4, left child of 4.
1 < 5, 1 < 4, 1 < 3, left child of 3.
Height = 3. Immediate children of 7: only 9 (one child).
Example 3: Insert 8, 3, 6, 10, 1, 7, 5
8 is root.
3 < 8, left child of 8.
6 > 3, right child of 3.
10 > 8, right child of 8.
1 < 8, 1 < 3, left child of 3.
7 > 3, 7 > 6, right child of 6.
5 < 8, 5 > 3, 5 < 6, left child of 6.
Immediate children of 6: 5 and 7 (two children).
Given the BST from sequence 5, 4, 7, 9, 8, 3, 1, inserting 6:
6 > 5 → right → 7
6 < 7 → left → NULL (7 has only a right child, 9)
6 becomes the left child of 7.
Inserting 10 into the same tree:
10 > 5 → right → 7 → 10 > 7 → right → 9 → 10 > 9 → right → NULL (9's left child is 8, right is NULL).
10 becomes the right child of 9.
To delete a node, first find it (O(h) time), then handle one of three situations.
Zero children (leaf node)
Simply remove the node. Set the parent's pointer to NULL. O(1) after finding the node.
One child
Delete the node the same way you would remove a node from a linked list: connect the node's parent directly to the node's single child. O(1) after finding the node.
Example: in a BST with root 6, left subtree rooted at 4 (with children 1 and 5, where 1 has children 2 and 3), deleting node 1. Node 1 has one child (a subtree with 2 → 3). Splice out 1 by pointing 4's left pointer to 2. The subtree 2 → 3 moves up.
Two children
This is the complex case. Three steps:
Find the in-order predecessor (IOP) or in-order successor (IOS) of the target node.
Swap the target node's key with the IOP or IOS key.
Remove the target node from its new position (which now has zero or one child, since the IOP has no right child and the IOS has no left child).
Example: delete 6 from the BST with structure 6 (root), left child 4 (children: 1 with subtree 2→3, and 5), right child 8 (children: 7 and 9).
IOP(6): go left to 4, then right to 5. IOP = 5.
IOS(6): go right to 8, then left to 7. IOS = 7.
Using IOP: swap 6 and 5, then remove 6 from where 5 was (now a leaf or one-child case). Result: 5 becomes root.
Using IOS: swap 6 and 7, then remove 6 from where 7 was. Result: 7 becomes root.
Both results are valid BSTs. Exam questions may accept either.
Insertion comparisons
Minimum: 1 (inserting into an empty tree or at the root's immediate child)
Maximum: n (tree is a degenerate chain)
IOP algorithm: left → right → right → right → ... (until NULL)
IOS algorithm: right → left → left → left → ... (until NULL)
Students often think a BST insertion can place a node in the middle of the tree. It cannot. New nodes are always inserted as leaves.
Students sometimes confuse "height" with "number of nodes on the longest path." Height counts edges, not nodes. A single-node tree has height 0, not 1.
When deleting a two-child node, students forget that after swapping with the IOP or IOS, the swapped node is guaranteed to have at most one child. You never face a recursive two-child deletion.
Students sometimes think IOP and IOS give different final tree shapes that are "wrong." Both are valid, and exams usually accept either.
⚠️ Building a BST from a given insertion order is a staple exam question. Practise until you can do it without thinking.
⚠️ Deletion with two children (IOP/IOS swap then remove) is the most commonly tested deletion scenario.
⚠️ Know how to identify immediate children of any node after building a tree from a sequence.
⚠️ Height calculation: count edges on the longest root-to-leaf path, not nodes.
True or false: inserting into a BST always requires exactly log(n) comparisons. False. It requires O(h) comparisons, and h can be as large as n in a degenerate tree.
Fill in the blank: to find the IOP of a node, go ____ once, then ____ as far as possible. Left, then right.
True or false: after deleting a node with two children using IOP swap, the BST property may be temporarily violated. False. The swap and removal are designed to maintain the BST property throughout.
Q: What is the minimum and maximum number of comparisons to insert a new node into a BST with n nodes?
A: Minimum is 1 (the tree is empty or the node goes directly below the root). Maximum is n (the tree is a degenerate chain and the new node goes at the bottom).
Q: Given insertion order 5, 4, 7, 9, 8, 3, 1, what are the immediate children of node 7?
A: Node 7 has one child: 9 (right child only).
Q: Describe the three cases for BST deletion.
A: Zero children: remove the node directly. One child: splice it out like a linked list node, connecting its parent to its child. Two children: find the IOP or IOS, swap keys, then remove the swapped node (which now has zero or one child).
Q: In the BST rooted at 6 with left subtree {4, 1, 5, 2, 3} and right subtree {8, 7, 9}, what is IOP(6) and IOS(6)?
A: IOP(6) = 5 (go left to 4, then right to 5, no further right child). IOS(6) = 7 (go right to 8, then left to 7, no further left child).
Q: After deleting 6 using IOP, what is the new root?
A: 5.
This material connects directly to balanced BSTs (AVL trees, red-black trees), which solve the degenerate-chain problem by guaranteeing h = O(log n). The deletion mechanics here carry over almost unchanged to those balanced variants, with added rotation steps.
The IOP/IOS concept reappears in iterator design for tree-based containers (like C++ std::set), where "next element" and "previous element" use exactly these traversal patterns.
Related Terms / Search Tags BST insert, BST delete, binary search tree removal, in-order predecessor, in-order successor, IOP, IOS, BST comparisons, degenerate tree, tree height, BST leaf insertion, two-child deletion, one-child deletion, UIUC data structures exam 2