Abstract flowing gradient in deep indigo and blue tones, smooth and luminous, evoking a modern digital learning atmosphere

Computer Science and programming articles. We do not sell courses.

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

Deletion checks

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.