BST Insertion, Search, and Deletion

A binary search tree (BST) is a binary tree that keeps its values in sorted order by enforcing one simple rule at every node: everything in the left subtree is smaller than the node, and everything in the right subtree is larger. That single invariant is what makes a BST useful — it turns tree traversal into a decision procedure, so you can insert, search, and delete values in time proportional to the tree’s height instead of scanning every element like you would with a plain list. This lesson builds a BST in Python from the ground up and walks through exactly how insertion, search, and deletion work, including the trickiest case — deleting a node with two children — and the mistakes that trip people up.

Overview / How it works

Every node in a BST stores a value plus two references: left and right, each either pointing to another node or to nothing (None). The BST property says that for any node n, every value in n.left‘s subtree is less than n.value, and every value in n.right‘s subtree is greater than n.value. This property holds recursively at every node, not just at the root, which is what lets you use the same left/right decision at any point in the tree.

Picture inserting the numbers 50, 30, 70, 20, 40, 60, and 80 one at a time, always starting the search for a spot at the root. 50 becomes the root. 30 is less than 50, so it becomes 50’s left child. 70 is greater than 50, so it becomes 50’s right child. 20 is less than 50 (go left) and less than 30 (go left again), so it becomes 30’s left child. Continuing this way for 40, 60, and 80 produces a tree where the smallest values live toward the left and the largest toward the right:

        50
       /  \
      30    70
     / \   / \
    20 40 60 80

Because of the BST property, an in-order traversal (left subtree, then node, then right subtree) always visits the nodes in ascending sorted order — that’s a useful sanity check when you’re debugging a BST implementation.

Search exploits the same property: compare the target to the current node, go left if the target is smaller, go right if it’s larger, and stop when you find a match or run off the tree (hit None). Each comparison eliminates one entire subtree from consideration, which is why search is fast — as long as the tree is reasonably balanced.

Insertion is search that doesn’t stop at None — it keeps going until it finds the empty spot where the new value belongs, then attaches a new node there. The recursive shape is elegant: _insert(node, value) returns the (possibly new) subtree rooted at that position, so each call along the path just reassigns node.left or node.right to whatever the recursive call returns.

Deletion is the one that needs care, because removing a node can leave a gap in the middle of the tree that has to be patched without breaking the BST property. There are three cases:

• The node is a leaf (no children) — just remove it by returning None in its place.
• The node has one child — the node is removed and replaced by that single child.
• The node has two children — you can’t just delete it, because you’d have to reattach two subtrees to one parent slot. Instead, find the node’s in-order successor (the smallest value in its right subtree, found by walking as far left as possible from node.right), copy that successor’s value into the node being "deleted", and then delete the successor node from the right subtree instead. The successor is guaranteed to have at most one child (a left child would contradict it being the smallest), so that recursive deletion falls into one of the two easier cases.

A crucial caveat: a plain BST does not guarantee balance. If you insert values in already-sorted order, every new node becomes the right child of the previous one, and the tree degenerates into something that behaves like a linked list. Self-balancing variants (AVL trees, red-black trees) exist specifically to prevent this by rearranging nodes after insert/delete so the height stays close to log n. This lesson covers the plain, unbalanced BST, which is still the right tool for many workloads and is the foundation those balanced trees build on.

Time and Space Complexity

Every operation’s cost is proportional to the tree’s height h, because each step moves one level down. The relationship between height and the number of nodes n is what determines whether you get logarithmic or linear behavior.

Operation	Average (balanced tree)	Worst case (skewed tree)	Why
Search	O(log n)	O(n)	Balanced: each comparison halves the remaining candidates, so height ≈ log n. Skewed: the tree is effectively a linked list of depth n, so a search may visit every node.
Insert	O(log n)	O(n)	Insertion is a search for the correct empty spot, so it has the same cost as search plus one constant-time node creation.
Delete	O(log n)	O(n)	Deletion needs a search to find the node (O(h)), and in the two-children case an additional walk to find the in-order successor, which is also bounded by O(h).

Space complexity is O(n) to store all n nodes. The recursive implementations shown below also use O(h) additional space on the call stack for the chain of pending calls — O(log n) for a balanced tree, but up to O(n) for a badly skewed one, which for very large skewed inputs can even exceed Python’s default recursion limit (around 1000) and raise a RecursionError. An iterative rewrite using an explicit loop avoids that risk when depth is a concern.

Examples

Example 1: Building a BST and searching it

This example wraps the node logic in a small BinarySearchTree class with insert, search, and an inorder traversal used to verify the tree is correctly sorted.

from typing import Optional

class TreeNode:
    def __init__(self, value: int) -> None:
        self.value = value
        self.left: Optional["TreeNode"] = None
        self.right: Optional["TreeNode"] = None


class BinarySearchTree:
    def __init__(self) -> None:
        self.root: Optional[TreeNode] = None

    def insert(self, value: int) -> None:
        self.root = self._insert(self.root, value)

    def _insert(self, node: Optional[TreeNode], value: int) -> TreeNode:
        if node is None:
            return TreeNode(value)
        if value < node.value:
            node.left = self._insert(node.left, value)
        elif value > node.value:
            node.right = self._insert(node.right, value)
        return node

    def search(self, value: int) -> bool:
        return self._search(self.root, value)

    def _search(self, node: Optional[TreeNode], value: int) -> bool:
        if node is None:
            return False
        if value == node.value:
            return True
        if value < node.value:
            return self._search(node.left, value)
        return self._search(node.right, value)

    def inorder(self) -> list[int]:
        result: list[int] = []
        self._inorder(self.root, result)
        return result

    def _inorder(self, node: Optional[TreeNode], result: list[int]) -> None:
        if node is not None:
            self._inorder(node.left, result)
            result.append(node.value)
            self._inorder(node.right, result)


def main() -> None:
    bst = BinarySearchTree()
    for value in [50, 30, 70, 20, 40, 60, 80]:
        bst.insert(value)

    print(bst.inorder())
    print(bst.search(40))
    print(bst.search(90))


if __name__ == "__main__":
    main()

Output:

[20, 30, 40, 50, 60, 70, 80]
True
False

Each insert call walks down from the root comparing the new value until it hits a None slot, exactly as traced above, producing the balanced tree shown earlier. inorder() confirms the values come out sorted. search(40) goes left at 50 (40 < 50), then right at 30 (40 > 30), and finds 40. search(90) goes right at 50, right at 70, right at 80, and falls off the tree into None, returning False.

Example 2: Deleting nodes, including the two-children case

from typing import Optional


class TreeNode:
    def __init__(self, value: int) -> None:
        self.value = value
        self.left: Optional["TreeNode"] = None
        self.right: Optional["TreeNode"] = None


def insert(node: Optional[TreeNode], value: int) -> TreeNode:
    if node is None:
        return TreeNode(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    return node


def find_min(node: TreeNode) -> TreeNode:
    current = node
    while current.left is not None:
        current = current.left
    return current


def delete(node: Optional[TreeNode], value: int) -> Optional[TreeNode]:
    if node is None:
        return None

    if value < node.value:
        node.left = delete(node.left, value)
    elif value > node.value:
        node.right = delete(node.right, value)
    else:
        if node.left is None:
            return node.right
        if node.right is None:
            return node.left
        successor = find_min(node.right)
        node.value = successor.value
        node.right = delete(node.right, successor.value)

    return node


def inorder(node: Optional[TreeNode], result: list[int]) -> None:
    if node is not None:
        inorder(node.left, result)
        result.append(node.value)
        inorder(node.right, result)


def main() -> None:
    root: Optional[TreeNode] = None
    for value in [50, 30, 70, 20, 40, 60, 80]:
        root = insert(root, value)

    result: list[int] = []
    inorder(root, result)
    print("Before delete:", result)

    root = delete(root, 30)
    result = []
    inorder(root, result)
    print("After deleting 30:", result)

    root = delete(root, 70)
    result = []
    inorder(root, result)
    print("After deleting 70:", result)

    root = delete(root, 50)
    result = []
    inorder(root, result)
    print("After deleting 50:", result)


if __name__ == "__main__":
    main()

Output:

Before delete: [20, 30, 40, 50, 60, 70, 80]
After deleting 30: [20, 40, 50, 60, 70, 80]
After deleting 70: [20, 40, 50, 60, 80]
After deleting 50: [20, 40, 60, 80]

Deleting 30 hits the two-children case (its children are 20 and 40): the in-order successor is 40 (the smallest value in 30’s right subtree, which has no left child), so 30’s node takes the value 40 and the original 40-node is removed. Deleting 70 works the same way with successor 80. Deleting the root, 50, is the most interesting: its successor is found by walking left from 70 (now holding value 80) down to 60, so the root becomes 60, and the old 60-node is spliced out. Notice the tree keeps its BST property and sorted in-order traversal after every deletion.

Example 3: Balanced vs. skewed insertion order

from typing import Optional


class TreeNode:
    def __init__(self, value: int) -> None:
        self.value = value
        self.left: Optional["TreeNode"] = None
        self.right: Optional["TreeNode"] = None


def insert(node: Optional[TreeNode], value: int) -> TreeNode:
    if node is None:
        return TreeNode(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    return node


def height(node: Optional[TreeNode]) -> int:
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))


def main() -> None:
    balanced_values = [50, 30, 70, 20, 40, 60, 80]
    balanced_root: Optional[TreeNode] = None
    for value in balanced_values:
        balanced_root = insert(balanced_root, value)

    sorted_values = [10, 20, 30, 40, 50, 60, 70]
    skewed_root: Optional[TreeNode] = None
    for value in sorted_values:
        skewed_root = insert(skewed_root, value)

    print("Balanced height:", height(balanced_root))
    print("Skewed height:", height(skewed_root))


if __name__ == "__main__":
    main()

Output:

Balanced height: 3
Skewed height: 7

Both trees hold the same 7 values, but the insertion order changes everything. The first list mixes high and low values so each insert roughly halves the remaining range, producing a height-3 tree where search touches at most 3 nodes. The second list is already sorted, so every new value is greater than everything inserted so far and always becomes the rightmost node’s right child — the tree degenerates into a 7-node chain, and searching for the last value visits all 7 nodes. This is the concrete meaning of "worst case O(n)" for a plain BST.

How it works step by step

Using the tree from Examples 1 and 2 (root 50, with 30/70 as children and 20/40/60/80 as grandchildren), here is search(40) traced one comparison at a time:

1. Start at the root, 50. Compare: 40 < 50, so move to node.left.
2. Now at 30. Compare: 40 > 30, so move to node.right.
3. Now at 40. Compare: 40 == 40, match found — return True.

And here is deleting 50 (the root, a two-children case) traced step by step:

1. Locate the node to delete: it’s the root itself, value 50, with both left (30’s subtree) and right (70’s subtree) present.
2. Because both children exist, find the in-order successor: start at node.right (70) and walk left as far as possible. 70 has a left child, 60; 60 has no left child, so 60 is the successor.
3. Copy the successor’s value into the node being deleted: the root’s value becomes 60.
4. Recursively delete 60 from the right subtree (rooted at 70). 60 is a leaf, so this call simply returns None in its place, detaching it.
5. The tree now has 60 at the root, with 40 (formerly 30, already merged in a prior deletion) on the left and 80 (formerly 70, already merged) on the right — still a valid BST, and an in-order traversal still comes out sorted.

Common Mistakes

Mistake 1: Deleting a two-children node by just detaching it

It’s tempting to handle deletion by simply returning None whenever you find the matching value, but that silently discards both of the node’s subtrees:

def delete_wrong(node, value):
    if node is None:
        return None
    if value < node.value:
        node.left = delete_wrong(node.left, value)
    elif value > node.value:
        node.right = delete_wrong(node.right, value)
    else:
        return None  # BUG: drops the matched node's children too!
    return node

Deleting 30 from the example tree this way would erase 20 and 40 along with it, corrupting the tree. The fix is the three-case logic shown in Example 2: return the single child directly when there’s zero or one child, and use the in-order-successor swap when there are two, so no subtree is ever silently dropped.

Mistake 2: A mutable default argument in an accumulator helper

It’s common to want a helper that records the path taken while searching, using a list parameter with a default value:

def collect_path(node, value, path=[]):
    # BUG: path=[] is created ONCE, when the function is defined,
    # and every call that omits path reuses that same list object.
    if node is None:
        return path
    path.append(node.value)
    if value == node.value:
        return path
    if value < node.value:
        return collect_path(node.left, value, path)
    return collect_path(node.right, value, path)

# collect_path(root, 40) -> [50, 30, 40]                       (looks correct)
# collect_path(root, 80) -> [50, 30, 40, 50, 70, 80]           (leftover values from the first call!)

Because Python evaluates default argument values exactly once, at function-definition time, every call that doesn’t pass path explicitly shares and mutates the same list, so results leak across unrelated calls. The fix is the standard Python idiom: default to None and create a fresh list inside the function body.

from typing import Optional


class TreeNode:
    def __init__(self, value: int) -> None:
        self.value = value
        self.left: Optional["TreeNode"] = None
        self.right: Optional["TreeNode"] = None


def insert(node: Optional[TreeNode], value: int) -> TreeNode:
    if node is None:
        return TreeNode(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    return node


def collect_path(node: Optional[TreeNode], value: int, path: Optional[list[int]] = None) -> list[int]:
    if path is None:
        path = []
    if node is None:
        return path
    path.append(node.value)
    if value == node.value:
        return path
    if value < node.value:
        return collect_path(node.left, value, path)
    return collect_path(node.right, value, path)


def main() -> None:
    root: Optional[TreeNode] = None
    for value in [50, 30, 70, 20, 40, 60, 80]:
        root = insert(root, value)

    print(collect_path(root, 40))
    print(collect_path(root, 80))


if __name__ == "__main__":
    main()

Output:

[50, 30, 40]
[50, 70, 80]

Now each call that omits path gets its own fresh list, so the second call is unaffected by the first — exactly the behavior the buggy version failed to provide.

Best Practices

• Use a plain BST when insertions arrive in a reasonably random order and you need ordered operations (in-order traversal, range queries, "next larger/smaller value") that a hash-based structure can’t give you.
• If insertion order might be sorted or near-sorted (a common real-world case: ingesting timestamped or already-sorted data), use a self-balancing structure — an AVL tree, a red-black tree, or in practice Python’s sortedcontainers.SortedList — instead of a plain BST, since a plain BST offers no protection against degrading to O(n).
• If you only need fast membership/lookup with no ordering requirement, prefer a set or dict: they give O(1) average lookup versus a BST’s O(log n) best case.
• Always implement deletion with the explicit three-case structure (leaf, one child, two children) — never assume a node can be removed by simply unlinking it.
• Never use a mutable default argument (path=[], acc={}) in a recursive helper; default to None and initialize inside the function body.
• Watch recursion depth on very large or adversarially-skewed trees; an iterative version using an explicit stack or loop avoids Python’s recursion limit entirely.
• When tracing or debugging a BST, run an in-order traversal — if the output isn’t sorted, the BST property has been violated somewhere.

Practice Exercises

• Exercise 1: Write a function is_valid_bst(root) that returns True if a binary tree satisfies the BST property at every node, not just between immediate parent and child (a common bug is checking only the direct children instead of the full valid range each node must fall within). Hint: pass down a (low, high) bound as you recurse.
• Exercise 2: Given a BST and a value k, write kth_smallest(root, k) that returns the k-th smallest value using an in-order traversal. For the tree built from [50, 30, 70, 20, 40, 60, 80], kth_smallest(root, 3) should return 40.
• Exercise 3: Write find_min_max(root) that returns a (minimum, maximum) tuple without doing a full traversal — exploit the BST property to reach the minimum and maximum in O(h) time each by only following left or right pointers.

Summary

• A BST maintains the invariant that every left subtree holds smaller values and every right subtree holds larger values, recursively, at every node.
• Search and insertion both work by walking down from the root, going left or right based on a single comparison at each step, until they hit a match (search) or an empty slot (insertion).
• Deletion has three cases: leaf (remove outright), one child (splice the child up), and two children (copy in the in-order successor’s value, then delete the successor, which has at most one child).
• Average-case time for search, insert, and delete is O(log n) on a balanced tree, but a plain BST offers no guarantee — a skewed insertion order degrades all three to worst-case O(n), same as a linked list.
• Space is O(n) for the nodes plus O(h) for the recursion stack, which is O(log n) balanced or up to O(n) skewed.
• Never delete a two-children node by simple detachment, and never use a mutable default argument in a recursive accumulator helper — both are classic, easy-to-miss bugs.
• Reach for a self-balancing BST or a hash-based structure instead of a plain BST when insertion order can’t be trusted to stay random.