How to implement a binary search tree with iterative insertion and deletion
Learning how to implement a binary search tree with iterative insertion and deletion is a useful exercise because the structure makes search paths visible. Each node stores one key and links to smaller keys on its left and larger keys on its right. The important goal is to preserve that ordering invariant after every update, not merely while creating the first version.
An iterative implementation follows those links with loops rather than recursive calls. Its control flow is explicit, and each operation needs only a fixed amount of extra working space, even if the tree later becomes tall. It also avoids Python’s recursion limit when keys arrive in sorted order, although avoiding recursion does not by itself make an unbalanced tree efficient.
Deletion is the delicate operation. A missing key changes nothing, a leaf can be detached immediately, and a node with one child can be replaced by that child. A node with two children needs the smallest key in its right subtree, after which the replacement must be reconnected without breaking any link.
The examples below use Python, integer keys, and a policy that ignores duplicate insertions. The same pointer logic transfers to C, where allocation and deallocation must be explicit. For learners in Sydney, Melbourne and Brisbane, the exercise works well in university labs, coding clubs and junior interview preparation without requiring a framework or paid tool.
Establish the ordering invariant
A binary search tree has a local rule and a global consequence. The local rule is that every key in a node’s left subtree is smaller than the node’s key, while every key in its right subtree is larger. The global consequence is that an in-order traversal visits keys in ascending order. Maintaining the local rule after insertion and deletion preserves that useful property.
Represent a node with a value and two child references; either child may be absent. The tree itself needs only one root reference. Keeping parent pointers is optional, and the implementation below avoids them by remembering the parent of the node currently being examined. That choice keeps the data structure compact and makes pointer changes visible.
Use a consistent duplicate policy. This version treats a second insertion of the same integer as a no-op, which avoids ambiguous children and keeps comparisons strict. If duplicates matter, add a count to each node, or place repeated values consistently on one side and document that rule.
Insert values with a downward loop
Insertion begins by creating a candidate node and handling the empty tree. Otherwise, start at the root and compare the candidate with the current node. A smaller value moves the search left, a larger value moves it right, and equality ends the operation. The loop stops only when it reaches an absent child, where the candidate can be attached.
There is no need to unwind a call stack after attachment because no recursive calls were made. Duplicate equality returns without changing a link, while the root case assigns the first node directly. These decisions keep the method’s loop invariant simple: current always points to a node whose subtree is the correct place to continue searching.
Running the method against ordered and reversed inputs is useful even when the result is correct, because it exposes how tall the tree becomes and makes the behaviour of an unbalanced structure visible. The broader hello ML tutorials collection includes related explanations for readers who want to compare pointer-based and array-based representations.
Search for keys and locate successors
Searching uses the same downward route. Compare the requested key with the current value, stop on equality, and otherwise move to the left or right child. If the route reaches an empty reference, the key is absent. The loop takes (O(h)) time, where (h) is the tree height; (h) is near (\log n) for a balanced tree but can reach (n) for a skewed one.
Two-child deletion depends on an in-order successor: the smallest key in the node’s right subtree. Start at the right child and keep moving left until no left child remains. That successor has no left subtree, so it can take the deleted node’s left branch. Its position and the deleted node’s right branch must then be rearranged carefully. The in-order predecessor—the largest key in the left subtree—is another valid choice, but the successor keeps every strictly larger key on the right.
The explicit left and right decisions remain as important in code as keeping left in Australian traffic, although the tree’s invariant supplies the actual rule. A contrasting design appears in implementing a splay tree, where recent searches reshape the structure to make repeated access more efficient.
Remove nodes without recursive calls
Deletion follows one of three structural cases. A leaf or a node with one child can be bypassed by replacing its link with the child or None. A node with two children requires the successor search just described. The method below relocates the successor node itself rather than copying only its value, so the resulting links are explicit.
The class is complete enough to paste into a Python file. Insertion and lookup are included for testing, while delete returns True only when a matching key was found and removed. The optional annotations make the intended node and tree shapes clear without changing the algorithm.
from dataclasses import dataclass
from typing import Optional
@dataclass
class Node:
value: int
left: Optional["Node"] = None
right: Optional["Node"] = None
class BinarySearchTree:
def __init__(self) -> None:
self.root: Optional[Node] = None
def insert(self, value: int) -> None:
new_node = Node(value)
if self.root is None:
self.root = new_node
return
current = self.root
while True:
if value < current.value:
if current.left is None:
current.left = new_node
return
current = current.left
elif value > current.value:
if current.right is None:
current.right = new_node
return
current = current.right
else:
return
def contains(self, value: int) -> bool:
current = self.root
while current is not None:
if value == current.value:
return True
if value < current.value:
current = current.left
else:
current = current.right
return False
def delete(self, value: int) -> bool:
parent: Optional[Node] = None
current: Optional[Node] = self.root
while current is not None and current.value != value:
parent = current
if value < current.value:
current = current.left
else:
current = current.right
if current is None:
return False
if current.left is None:
replacement = current.right
elif current.right is None:
replacement = current.left
else:
successor_parent = current
successor = current.right
while successor.left is not None:
successor_parent = successor
successor = successor.left
if successor_parent is current:
successor.left = current.left
else:
successor_parent.left = successor.right
successor.left = current.left
successor.right = current.right
replacement = successor
if parent is None:
self.root = replacement
elif parent.left is current:
parent.left = replacement
else:
parent.right = replacement
return True
tree = BinarySearchTree()
for key in (8, 3, 10, 1, 6, 14, 4, 7, 13):
tree.insert(key)
assert tree.contains(6)
assert tree.delete(6)
assert not tree.contains(6)
assert tree.delete(99)
assert tree.delete(8)
assert tree.root is not None
assert tree.root.value == 10
During deletion, parent records where the current node is attached, while successor_parent records where the successor is attached. These may be different nodes. Reconnecting through the original parent is essential; attaching the replacement to successor_parent instead would incorrectly add a second link and could create a cycle.
The algorithm also handles an empty tree, deleting an absent value, and removing the last remaining node. In C, free the node that is actually discarded, and ensure the relocated successor is not freed as well. Small helper functions can add ordering checks, but the core update logic remains the same.
Verify behaviour and compare alternatives
Test each structural case rather than checking only the final root. A compact sequence can build a mixed tree, remove an internal node with two children, remove a missing key, and then remove the root. Assertions make regressions visible without requiring a testing framework.
Insertion checks
- The first value becomes the root when the tree is empty.
- A repeated value leaves every link unchanged under the chosen duplicate policy.
- A smaller value follows leftward links until an empty child is reached.
- A larger value follows rightward links until an empty child is reached.
Deletion checks
- An absent key returns
Falsewithout modifying the tree. - A leaf is removed by replacing its parent’s link with
None. - A one-child node is replaced directly by that child.
- A two-child node is replaced by its in-order successor without violating the ordering invariant.
These checks target links rather than only values, which is where most implementation mistakes appear. An in-order traversal after each mutation provides another simple verification method because its output must remain sorted.
The practical choices differ in how they guarantee path length and how much control they leave to the programmer:
| Approach | Search cost | Insertion or deletion | Extra working space | Main characteristic |
|---|---|---|---|---|
| Plain iterative BST | (O(h)) | (O(h)) | (O(1)) | Simple pointer updates, but height depends on insertion order |
| Recursive BST | (O(h)) | (O(h)) | (O(h)) call stack | Shorter code, with recursion depth as a limitation |
| Splay tree | (O(\log n)) amortised | (O(\log n)) amortised | (O(1)) | Recent accesses move nodes toward the root |
| AVL tree | (O(\log n)) worst case | (O(\log n)) worst case | (O(1)) | Strict balance requires extra rotations and code |
In Australia’s fintech, logistics, healthcare and public-service sectors, production systems may need guaranteed lookup bounds and auditable update behaviour. The Privacy Act 1988 adds governance duties for many health datasets, which no data structure can address. An iterative binary search tree provides a transparent foundation for understanding ordered indexes, while balanced trees and tested libraries carry the load when logarithmic access must be guaranteed.