5.2 Binary Search Trees: Insertion, Deletion, and Search
Prerequisites: Binary Tree Structure and Recursion, approximately 35 minutes. This lesson uses unique integer keys and implements search, insertion, three types of deletion, global validation, and range queries. Performance is consistently analyzed using tree height
h.
Ordering Rules Are a Global Invariant
A BST adds a global ordering rule to an ordinary binary tree:
For each node, all keys in the left subtree are less than the current key, and all keys in the right subtree are greater than the current key.
The word “all” matters. In the tree below, the immediate children appear correct, yet node 12 is placed within the left subtree of the root node 10. Since 12 is greater than 10, this violates the BST property.
10
/ \
5 15
\
12 ← Greater than 10, yet still in the left subtree of 10This page treats a BST as a set of unique integer keys. Duplicate insertion leaves the tree unchanged, returns False, and preserves size. If your application requires multiple entries with the same key, modify the node to store a list, or add a count field; never arbitrarily place equal keys into one subtree without explicit justification.
Finding: Traverse One Subtree at a Time
In the sample tree, searching for 60:
50 → 70 → 60
60 > 50, go right
60 < 70, go leftHeight h counts edges in a nonempty tree. Search checks at most h+1 nodes and takes O(h + 1) time; an empty-tree lookup takes constant time. It can only be written as O(log n) when h = O(log n).
A failed search also follows a single path to a null link. It does not need to traverse the other side, because the BST invariant rules out the presence of that key.
Insert: Attaching to a Gap Along the Search Path
Insertion follows the same search path as a failed lookup. The difference is that when the path reaches a null link, a new node is created and the link is reconnected to the parent node.
Duplicate keys are not processed to create new nodes on this page. This decision impacts size, deletion semantics, validation boundaries, and in-order traversal results, so the code handles it within insert.
Deletion: What Should the Parent Node Reconnect To?
After locating the target node, handle it based on the number of children:
No Children
Return an empty link. The parent node no longer points to the target.
One Child
Return the sole child. The parent node skips over the target and directly connects to its subtree.
Two Children
Both the left and right subtrees of the target must be preserved. The algorithm selects the smallest key in the right subtree, its inorder successor:
- Copy the successor's key into the target node.
- Remove the original successor node from the right subtree.
- Reattach the modified right subtree.
The successor has no left child, so the second deletion will either fall into the "no children" or "one child" case.
Complete Implementation
This program runs independently. Public methods maintain root and size. Recursive deletion returns the updated subtree root; search and insertion use loops. Integer-key checks prevent a value such as NaN, which is neither less nor greater, from falling through to the deletion branch.
def require_int_key(key):
if not isinstance(key, int):
raise TypeError("key must be an integer")
class TreeNode:
def __init__(self, key):
require_int_key(key)
self.key = key
self.left = None
self.right = None
def is_valid_bst(root):
"""Validates the strict BST invariant using open lower and upper bounds."""
def validate(node, lower, upper):
if node is None:
return True
if lower is not None and node.key <= lower:
return False
if upper is not None and node.key >= upper:
return False
return (
validate(node.left, lower, node.key)
and validate(node.right, node.key, upper)
)
return validate(root, None, None)
def range_query(root, low, high):
"""Returns keys in ascending order within the closed range [low, high]."""
require_int_key(low)
require_int_key(high)
if low > high:
return []
result = []
def visit(node):
if node is None:
return
if node.key > low:
visit(node.left)
if low <= node.key <= high:
result.append(node.key)
if node.key < high:
visit(node.right)
visit(root)
return result
class BinarySearchTree:
def __init__(self):
self.root = None
self.size = 0
def search(self, key):
require_int_key(key)
current = self.root
while current is not None:
if key == current.key:
return current
if key < current.key:
current = current.left
else:
current = current.right
return None
def insert(self, key):
require_int_key(key)
if self.root is None:
self.root = TreeNode(key)
self.size = 1
return True
parent = None
current = self.root
while current is not None:
parent = current
if key == current.key:
return False
if key < current.key:
current = current.left
else:
current = current.right
if key < parent.key:
parent.left = TreeNode(key)
else:
parent.right = TreeNode(key)
self.size += 1
return True
def delete(self, key):
require_int_key(key)
self.root, deleted = self._delete(self.root, key)
if deleted:
self.size -= 1
return deleted
def _delete(self, node, key):
if node is None:
return None, False
if key < node.key:
node.left, deleted = self._delete(node.left, key)
return node, deleted
if key > node.key:
node.right, deleted = self._delete(node.right, key)
return node, deleted
if node.left is None:
return node.right, True
if node.right is None:
return node.left, True
successor = node.right
while successor.left is not None:
successor = successor.left
node.key = successor.key
node.right, _ = self._delete(node.right, successor.key)
return node, True
def inorder(self):
result = []
def visit(node):
if node is None:
return
visit(node.left)
result.append(node.key)
visit(node.right)
visit(self.root)
return result
def range_query(self, low, high):
return range_query(self.root, low, high)
def is_valid(self):
return is_valid_bst(self.root)
tree = BinarySearchTree()
for key in [50, 30, 70, 20, 40, 60, 80]:
assert tree.insert(key)
assert tree.inorder() == [20, 30, 40, 50, 60, 70, 80]
assert tree.size == 7
assert tree.search(60).key == 60
assert tree.search(99) is None
assert not tree.insert(60)
assert tree.size == 7
assert tree.range_query(35, 70) == [40, 50, 60, 70]
assert tree.is_valid()
assert tree.delete(20) # Leaf node
assert tree.delete(30) # Now has only one child: 40
assert tree.delete(50) # Root node with two children
assert not tree.delete(999) # Key not present
assert tree.inorder() == [40, 60, 70, 80]
assert tree.size == 4
assert tree.is_valid()Why must bounds be passed during validation?
Local checks can only guarantee:
node.left.key < node.key < node.right.keyLocal checks do not constrain deeper descendants. In root 10’s left subtree, every key must lie in (-∞, 10). Entering node 5’s right subtree tightens that interval to (5, 10), so node 12 fails the upper bound.
is_valid_bst checks key ordering; it assumes an acyclic binary tree without shared children and does not detect object-graph cycles. Its bounds form open intervals, matching the strict unique-key rule. If the data structure employs other duplicate key strategies, boundary comparisons must be adjusted accordingly.
How to prune range queries
For the closed interval [35, 70]:
- If the current key is at most 35, its left subtree cannot contribute a result.
- If the current key is at least 70, its right subtree cannot contribute a result.
- If the key lies in the interval, append it at its inorder position.
The returned keys are already ascending. With k results, visiting costs O(h + k + 1); a chain or a query covering every key may take O(n). The returned keys use Θ(k) output space, and recursion needs O(h+1) auxiliary space. If low > high, the function returns an empty list.
Complexity and Shape
The table counts integer comparison as unit work; large Python integers add bit-length costs. The Θ(n) output space of an inorder list is separate. Empty-tree operations take constant time.
| Operation | Time | Iterative auxiliary space | Recursive auxiliary space |
|---|---|---|---|
| Search | O(h + 1) | O(1) | If recursively implemented then O(h + 1) |
| Insert | O(h + 1) | O(1) | If recursively implemented then O(h + 1) |
| Delete | O(h + 1) | Recursive implementation on this page is not applicable | O(h + 1) |
| In-order traversal | O(n) | O(h + 1) | O(h + 1) |
| Range query | O(h + k + 1), Worst case O(n) | depends on the implementation | This page is O(h + 1) |
Inserting 1, 2, 3, 4, 5 in order produces:
1
\
2
\
3
\
4
\
5The tree still satisfies the BST invariant but has h = n - 1. A standard BST lacks self-balancing mechanisms, so input order affects its shape. Search and insertion use loops, but deletion, inorder traversal, and validation still recurse; a deep chain can hit Python’s recursion limit.
BST, Hash Tables, and Ordered Containers
| Capability | Ordinary Hash Table | Unbalanced BST | Balanced Ordered Container |
|---|---|---|---|
| Exact Lookup | Expected O(1), worst-case linear | O(h + 1) | O(log n) |
| In-order Traversal | Requires separate sorting | O(n) | O(n) |
| Lower/Upper Bound | Typically requires scanning | O(h + 1) | O(log n) |
| Range Query | Usually requires scanning or maintains extra indexing | O(h + k + 1) | O(log n + k) |
| Input Order Affects Tree Height | Not applicable | Yes | Height constrained by balancing rules |
Java TreeMap publicly declares the use of red-black trees and guarantees logarithmic time for fundamental operations. C++ standards specify comparator ordering and logarithmic complexity for ordered associative containers like set and map, but do not require any specific node layout. Python's dict iteration order follows insertion order, not the sorted order of keys.
Common Errors
Root is not updated after deletion
The root may be replaced by its only child or become an empty tree. For class methods, write self.root = .... For functional interfaces, let the caller receive the newly returned root.
After deleting a node with two children, two identical keys remain
After copying the successor key, you must also remove the original successor node from the right subtree. Copying without deletion violates key uniqueness. Node identity also matters: an external reference to the target may still refer to a live tree node whose key has changed to the successor’s key. The original successor node is detached. This example does not promise that a node reference always identifies the same key; callers must not modify keys or links outside the tree’s methods.
Duplicate insertion still increases size
First check for equality, then create the node and increment the count. insert returns a boolean indicating whether it added a node.
Using float("-inf") as a universal boundary
Floating-point infinity works for numeric keys but not for strings or custom comparable objects. Code should use None to denote unboundedness, and only compare boundaries when they actually exist.
Treating implementation details as language guarantees
The fact that a common C++ standard library implementation uses a red-black tree does not mean the C++ standard mandates such an implementation. Professional documentation should reference publicly stated complexity and ordering contracts, not internal implementation choices.
Debugging Order
- Document the semantics of the repeat-key policy and comparator.
- Perform an in-order traversal after each change to verify strict monotonicity.
- Simultaneously compare
sizewith the length of the in-order traversal result. - Test edge cases individually: empty tree, single-node tree, leaf node, single-child root, two-child root, and missing keys.
- Construct deeply violating nodes to validate upper and lower bounds.
- Insert an ordered sequence, record the resulting height, and verify the stated complexity analysis.
Hands-on Verify Global Invariants
- Implement
min_key,max_key,floor, andceiling. - Change the duplicate key strategy to node counting, and list all methods that need to be synchronized in the update.
- Write five assertions for
delete, covering three child counts, root node cases, and missing keys. - Write a faulty local validator, then use a tree with a deeper ordering violation to show that it wrongly accepts the tree.
- Compare tree height after random-order versus sorted-order insertions, don’t just compare runtime performance.
Check Global Order and Height
A BST's decision rule is based on the upper and lower bounds of the entire subtree, rather than the immediate children alone. Search and insertion follow one path; two-child deletion also locates and removes a successor. Total time remains O(h + 1). A standard BST can degrade into a linear chain under ordered input, so it has no general logarithmic guarantee. When deleting, the root node and nodes with two children are the most critical cases to test repeatedly, since the caller must handle the new subtree root.
Next, go to Tree Traversals, where we separate the decision of "which branch to take" from the moment of "visiting the current node." The height issues caused by ordered input are left for Chapter 6: Balanced Trees to be addressed through rotations and color constraints.