Algo Binary Search Trees

Binary Search Trees (BST)

When to Use

• Implementing a BST from scratch for an interview, assignment, or as a building block for another data structure.
• Explaining or reasoning about BST time complexity (search/insert/delete/traversal) and why sorted input is a worst case.
• Debugging a broken delete (especially the two-children case) or successor/predecessor logic.
• Deciding whether a plain BST is sufficient or whether you need a self-balancing variant (AVL, Red-Black) for guaranteed O(log n).
• Needing inorder (sorted-order) or level-order (BFS) traversal of a tree of ordered values.

Version Compatibility

Pure Python standard library only — collections.deque, typing. Works on Python ≥3.10 (uses X | None union syntax); for 3.8/3.9 replace with Optional[X].

Prerequisites

• No external packages required.
• Helpful prior concepts: algo-complexity-analysis (Big-O basics), algo-linear-binary-search (binary search on sorted arrays, for contrast).
• For guaranteed O(log n) instead of amortized/average behavior, see algo-avl-trees or algo-red-black-trees.

Invariant: for every node, all values in the left subtree < node value < all values in the right subtree (no duplicates stored; duplicates are treated as no-ops on insert).

Complexity

Worst case occurs on sorted (or reverse-sorted) input, which degenerates the tree into a linked list — use AVL or Red-Black tree to guarantee O(log n).

Goal: a correct, iterative BST supporting search/insert/delete plus ordering queries (min, max, successor, predecessor) and two traversal orders.

Approach: store left/right/parent pointers per node; keep insert/search iterative (O(height) stack-free); implement delete via the classic three-case rule, using _transplant to splice a subtree in place of a node.

from collections import deque
from typing import Any


class Node:
    def __init__(self, value: Any) -> None:
        self.value = value
        self.left = self.right = self.parent = None


class BST:
    def __init__(self) -> None:
        self.root: Node | None = None

    # --- Insert (iterative) ---
    def insert(self, value: Any) -> Node:
        """Insert value, returning the new (or existing, if duplicate) node."""
        if not self.root:
            self.root = Node(value)
            return self.root
        node = self.root
        while True:
            if value < node.value:
                if node.left is None:
                    node.left = Node(value)
                    node.left.parent = node
                    return node.left
                node = node.left
            elif value > node.value:
                if node.right is None:
                    node.right = Node(value)
                    node.right.parent = node
                    return node.right
                node = node.right
            else:
                return node  # duplicate: no-op

    # --- Search (iterative) ---
    def search(self, value: Any) -> Node | None:
        node = self.root
        while node:
            if value == node.value:
                return node
            node = node.left if value < node.value else node.right
        return None

    # --- Min / Max ---
    def find_min(self, node: Node | None = None) -> Node | None:
        node = node or self.root
        if not node:
            return None
        while node.left:
            node = node.left
        return node

    def find_max(self, node: Node | None = None) -> Node | None:
        node = node or self.root
        if not node:
            return None
        while node.right:
            node = node.right
        return node

    # --- Successor / Predecessor ---
    def successor(self, node: Node) -> Node | None:
        if node.right:
            return self.find_min(node.right)
        p = node.parent
        while p and node == p.right:
            node, p = p, p.parent
        return p

    def predecessor(self, node: Node) -> Node | None:
        if node.left:
            return self.find_max(node.left)
        p = node.parent
        while p and node == p.left:
            node, p = p, p.parent
        return p

    # --- Delete ---
    def delete(self, value: Any) -> bool:
        """Delete value if present. Returns True if a node was removed."""
        node = self.search(value)
        if not node:
            return False
        self._delete_node(node)
        return True

    def _delete_node(self, node: Node) -> None:
        if node.left and node.right:
            succ = self.find_min(node.right)
            node.value = succ.value
            self._delete_node(succ)  # succ has at most one child (its right)
        else:
            child = node.left or node.right
            self._transplant(node, child)

    def _transplant(self, u: Node, v: Node | None) -> None:
        """Replace subtree rooted at u with subtree rooted at v."""
        if not u.parent:
            self.root = v
        elif u == u.parent.left:
            u.parent.left = v
        else:
            u.parent.right = v
        if v:
            v.parent = u.parent

    # --- Traversals ---
    def inorder(self) -> list[Any]:
        """Return values in sorted order."""
        result: list[Any] = []

        def _rec(n):
            if n:
                _rec(n.left)
                result.append(n.value)
                _rec(n.right)

        _rec(self.root)
        return result

    def level_order(self) -> list[Any]:
        """Return values in BFS (level-by-level) order."""
        if not self.root:
            return []
        result, q = [], deque([self.root])
        while q:
            n = q.popleft()
            result.append(n.value)
            if n.left:
                q.append(n.left)
            if n.right:
                q.append(n.right)
        return result

    def __contains__(self, value: Any) -> bool:
        return self.search(value) is not None


def demo() -> None:
    """Self-check: build a tree, verify invariants hold after insert/delete."""
    bst = BST()
    for v in [50, 30, 70, 20, 40, 60, 80]:
        bst.insert(v)
    assert bst.inorder() == [20, 30, 40, 50, 60, 70, 80]
    assert 40 in bst and 999 not in bst

    n40 = bst.search(40)
    assert bst.successor(n40).value == 50
    assert bst.predecessor(n40).value == 30

    assert bst.delete(30) is True   # two children (20 has none, but 30 has left=20)
    assert 30 not in bst
    assert bst.inorder() == [20, 40, 50, 60, 70, 80]
    assert bst.delete(999) is False

    print("All BST checks passed.")


if __name__ == "__main__":
    demo()

Delete: Three Cases

Pitfalls

• Sorted input degenerates to O(n): inserting [1,2,3,4,5] creates a linked list; use a self-balancing tree (AVL, Red-Black) for production use where input order isn't controlled.
• Inorder successor during deletion: after copying the successor's value to the deleted node, you must delete the successor node — not the original node again (recursing on succ, not node, avoids this).
• Parent pointer consistency: when implementing with parent pointers, only set v.parent in _transplant if v is not None, or you'll crash on leaf deletion.
• Recursive height/traversal on deep trees: Python's default recursion limit (~1000) is hit on degenerate (near-linear) trees; use iterative traversal (e.g. an explicit stack, like level_order's BFS) for untrusted input sizes.
• Duplicates: this implementation silently ignores inserting a value already present; decide explicitly whether your use case needs a count/multiset instead.

See Also

• algo-avl-trees — self-balancing BST guaranteeing O(log n) via rotations.
• algo-red-black-trees — another self-balancing BST, used by many standard library map/set implementations.
• algo-linear-binary-search — binary search over a sorted array (no explicit tree structure).
• algo-complexity-analysis — Big-O fundamentals referenced throughout this skill.