Data Structure

Binary Search Tree

“The Unbalanced Ancestor”

Search: O(h)

Space: O(n)

Self-Balancing: No

History

The Binary Search Tree (BST) is the grandfather of modern hierarchical data structures. While the concept of binary search on arrays existed earlier, the dynamic pointer-based tree structure emerged in the 1960s as a way to handle changing datasets.

It is the simplest form of a "sorted" tree. It represents the ideal of $O(\log n)$ performance, but without any safety rails to guarantee it.

Core Property

The Binary Search Property

For every node, all nodes in its Left Subtree are smaller, and all nodes in its Right Subtree are larger. This simple rule allows us to cut the search space in half with every step down the tree.

How It Works

A BST relies on simple comparisons to navigate.

The Mechanics

Search: Start at the root. If the value is what you want, stop. If smaller, go left. If larger, go right. Repeat.
Insert: Perform a search until you hit a "null" spot (a dead end). Plant the new node there.
Delete: This is the tricky part.

Leaf node: Just snip it off.
One child: Replace the node with its child.
Two children: Find the "In-Order Successor" (smallest node in the right subtree), swap values, and delete that successor.

SearchO(h)

Time depends on height ($h$). In a balanced tree, $h = log n$. In a line, $h = n$.

InsertO(h)

We have to traverse from root to leaf to find the insertion spot.

DeleteO(h)

Finding the node and its successor takes time proportional to the tree's depth.

SpaceO(n)

We need to store every element. No extra overhead for balancing metadata.

Code Walkthrough

Complete data structure implementations in multiple programming languages. Select a language to view idiomatic code.

1class TreeNode:
2    """Node for Binary Search Tree."""
3    def __init__(self, val: int):
4        self.val = val
5        self.left: TreeNode | None = None
6        self.right: TreeNode | None = None
7
8
9class BST:
10    """Binary Search Tree with insert, search, and delete operations."""
11    def __init__(self):
12        self.root: TreeNode | None = None
13
14    def insert(self, val: int) -> None:
15        """Insert a value into the BST."""
16        if not self.root:
17            self.root = TreeNode(val)
18            return
19
20        curr = self.root
21        while True:
22            if val < curr.val:
23                if curr.left is None:
24                    curr.left = TreeNode(val)
25                    return
26                curr = curr.left
27            else:
28                if curr.right is None:
29                    curr.right = TreeNode(val)
30                    return
31                curr = curr.right
32
33    def search(self, val: int) -> TreeNode | None:
34        """Search for a value in the BST."""
35        curr = self.root
36        while curr:
37            if val == curr.val:
38                return curr
39            elif val < curr.val:
40                curr = curr.left
41            else:
42                curr = curr.right
43        return None
44
45    def delete(self, val: int) -> None:
46        """Delete a value from the BST."""
47        self.root = self._delete_recursive(self.root, val)
48
49    def _delete_recursive(self, node: TreeNode | None, val: int) -> TreeNode | None:
50        if not node:
51            return None
52
53        if val < node.val:
54            node.left = self._delete_recursive(node.left, val)
55        elif val > node.val:
56            node.right = self._delete_recursive(node.right, val)
57        else:
58            # Node found - handle three cases
59            if not node.left:
60                return node.right
61            if not node.right:
62                return node.left
63
64            # Two children: find in-order successor
65            successor = self._find_min(node.right)
66            node.val = successor.val
67            node.right = self._delete_recursive(node.right, successor.val)
68
69        return node
70
71    def _find_min(self, node: TreeNode) -> TreeNode:
72        """Find the minimum value node in a subtree."""
73        while node.left:
74            node = node.left
75        return node