/Programming

There's a moment when almost every programmer runs into an uncomfortable question: if I already have arrays and lists, why do I need to learn trees? The answer starts with a very concrete problem. If you have a sorted array with a million elements, finding a value is fast — binary search gets you there in about twenty comparisons, thanks to O(log n). The problem shows up when you need to insert or remove something. At that point, the array forces you to shift potentially half of memory to keep things sorted, and what was fast turns into a painful O(n). The binary search tree exists precisely to solve this trade-off. It gives you the same logic as binary search, but organized so that inserting and removing also cost, on average, O(log n). It's not free — as you'll see later, there's a price to pay when the tree becomes unbalanced — but for most practical cases, it's one of the most elegant structures you'll ever implement. It's also a great way to test whether you truly understand recursion, references, and algorithmic complexity, because none of those three things can be faked here. This article implements a BST from scratch, in Python, covering insertion, search, deletion, traversals, testing, and the limitations that will, sooner or later, push you toward learning about self-balancing trees. ## What a binary search tree actually is A binary search tree is a structure of nodes where each node has at most two children — one on the left and one on the right — and obeys a single rule that underpins everything else: for any node in the tree, every value in its left subtree is smaller than it, and every value in its right subtree is larger. This property applies recursively, which means each subtree is itself a valid binary search tree. Imagine inserting the values 8, 3, 10, 1, 6, 14, 4, and 7 in that order. The 8 becomes the root. The 3 is smaller, so it goes left. The 10 is larger, so it goes right. The 1 is smaller than 8 and smaller than 3, so it descends to the left of the 3. And so on, always comparing and deciding left or right, until it finds an empty spot. The result is a tree where, if you traverse it the right way, the values come out in ascending order — something we'll explore in the traversals section. ## The base data structure Before any algorithm, we need two building blocks: the node and the tree. The node holds a value and two references, one for each child, which start as `None` until the node has descendants. ```python class Node: def __init__(self, value): self.value = value self.left = None self.right = None class BinarySearchTree: def __init__(self): self.root = None ``` Notice that the tree itself doesn't hold much more than a reference to the root. The entire structure lives in the chain of nodes linked through `left` and `right`. This is a deliberately minimal structure — the complexity isn't in the data we store, it's in the logic of where we place it. ## Insertion: the first algorithm to implement Inserting a value into a BST always follows the same reasoning: start at the root, compare the new value with the current node's value, decide whether to go left or right, and repeat until you find an empty spot where the new node can sit. ```python class BinarySearchTree: def __init__(self): self.root = None def insert(self, value): if self.root is None: self.root = Node(value) return self._insert_recursive(self.root, value) def _insert_recursive(self, node, value): if value < node.value: if node.left is None: node.left = Node(value) else: self._insert_recursive(node.left, value) elif value > node.value: if node.right is None: node.right = Node(value) else: self._insert_recursive(node.right, value) # if value == node.value, we choose to ignore duplicates ``` This recursive version is the most readable, which is why it's the one that shows up in most books. But it's worth having the iterative version too, because in very deep, unbalanced trees, recursion can exhaust the call stack. The iterative version avoids that risk by trading function calls for a simple `while` loop. ```python def insert_iterative(self, value): 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 # duplicate, do nothing ``` In practice, the difference only matters in trees with thousands of levels, which is rare if the tree is reasonably balanced. But it's the kind of detail that separates someone who just copied the algorithm from someone who understands its limits. ## Search: the simplest operation, but the most revealing Search follows the same logic as insertion, except that instead of creating a new node when you reach an empty spot, you simply report that the value doesn't exist. ```python def search(self, value): return self._search_recursive(self.root, value) def _search_recursive(self, node, value): if node is None: return False if value == node.value: return True if value < node.value: return self._search_recursive(node.left, value) return self._search_recursive(node.right, value) ``` This operation is the whole reason the BST exists. With each comparison, you eliminate half of the remaining candidates, exactly like binary search on an array. In a balanced tree with a million nodes, you find any value in about twenty comparisons — O(log n). But there's a hidden condition in that sentence: "in a balanced tree." If the tree is degenerate — for example, if you inserted the values already sorted, 1, 2, 3, 4, 5 — every node only has a right child, and the tree effectively becomes a linked list. In that case, finding the last value costs O(n), exactly what you were trying to avoid by using a tree in the first place. We'll come back to this problem later, because it's the most important limitation of a plain BST. ## Deletion: the part that usually trips people up If insertion and search were straightforward, deletion is where most tutorials lose the reader — and where it's worth slowing down. The reason is that removing a node can leave a "hole" in the tree, and there are three different situations depending on how many children the removed node has. **Node with no children (a leaf).** This is the simplest case: just disconnect the parent's reference to that node, replacing it with `None`. **Node with one child.** The removed node is replaced directly by its only child. It's like skipping a link in a chain: the parent starts pointing to the grandchild. **Node with two children.** This is the interesting case. You can't simply remove the node, because that would orphan two subtrees. The classic solution is to find the *in-order successor* — the smallest value in the right subtree, which is always the next value larger than the removed node — copy that value into the node you're removing, and then remove the successor from its original position (where, by construction, it never has a left child, which reduces the problem to one of the two previous cases). ```python def delete(self, value): self.root = self._delete_recursive(self.root, value) def _delete_recursive(self, node, value): if node is None: return None if value < node.value: node.left = self._delete_recursive(node.left, value) elif value > node.value: node.right = self._delete_recursive(node.right, value) else: # We found the node to remove if node.left is None: return node.right if node.right is None: return node.left # Node with two children: find the in-order successor successor = self._find_min(node.right) node.value = successor.value node.right = self._delete_recursive(node.right, successor.value) return node def _find_min(self, node): while node.left is not None: node = node.left return node ``` Notice the elegance of this solution: instead of treating the two-children case as something entirely new, we reduce it to a problem we already know how to solve. This is a common pattern in tree algorithms — reduce the hard case to a combination of the easy cases, rather than writing new logic for every situation. You could have chosen the *in-order predecessor* (the largest value in the left subtree) instead of the successor — both work equally well, and it's an implementation choice, not a fixed rule. ## Traversals: the different ways to visit the tree Traversing a tree means visiting all its nodes in a specific order. There are three classic depth-first traversals, and each serves a different purpose. **In-order traversal** (left, node, right) is the most important one for a BST, because it produces the values in ascending order. It's the fastest way to "export" the tree as a sorted list. ```python def in_order(self): result = [] self._in_order_recursive(self.root, result) return result def _in_order_recursive(self, node, result): if node is not None: self._in_order_recursive(node.left, result) result.append(node.value) self._in_order_recursive(node.right, result) ``` **Pre-order traversal** (node, left, right) visits the root before the children, which makes it useful when you need to recreate the tree's structure — for example, to serialize and later reconstruct the tree exactly as it was. **Post-order traversal** (left, right, node) visits the children before the node, which is useful when you need to safely delete the tree, freeing child nodes first, or when you're computing something that depends on the results of subtrees, like the size or height of each branch. There's also a fourth traversal, breadth-first (BFS), which visits the tree level by level instead of going deep first. It's not as common in the day-to-day operations of a BST, but it's essential if you need to print the tree in a readable way or find the node closest to the root that satisfies a condition. ## The problem of imbalance We've reached the point that any honest article about BSTs has to face: this structure, as we've implemented it, guarantees nothing about its own shape. If you insert the values 1, 2, 3, 4, 5, 6, 7 in order, each value is larger than the previous one, so every new node always goes to the right. The result isn't a tree — it's a linked list in disguise, with a height of 7 instead of the ideal height of about 3. ```python tree = BinarySearchTree() for value in range(1, 8): tree.insert(value) # The tree has degenerated: every node only has a right child ``` In this degenerate situation, every operation that was supposed to cost O(log n) — insertion, search, and deletion — now costs O(n), because each one effectively walks through every node. You've lost exactly the advantage that led you to choose a tree over an array in the first place. This problem is what motivates self-balancing trees, like AVL trees and Red-Black trees, which most standard libraries use internally (Java's `TreeMap` and C++'s `std::map`, for example, are typically Red-Black trees). These structures perform automatic rotations during insertion and deletion to ensure the tree never becomes too unbalanced, keeping O(log n) even in the worst case. Implementing them is a natural next step after this article, but it requires a solid grasp of the fundamentals we just built — no AVL rotation will make sense if you don't first understand why it's necessary. ## Testing the implementation A data structure is only complete once you know it works, and the best way to prove that is to write a small set of tests that exercise the cases we've discussed. ```python def test_bst(): tree = BinarySearchTree() for value in [8, 3, 10, 1, 6, 14, 4, 7]: tree.insert(value) assert tree.search(6) is True assert tree.search(99) is False assert tree.in_order() == [1, 3, 4, 6, 7, 8, 10, 14] tree.delete(3) # node with two children assert tree.search(3) is False assert tree.in_order() == [1, 4, 6, 7, 8, 10, 14] tree.delete(14) # leaf node assert tree.search(14) is False print("All tests passed.") test_bst() ``` This small block doesn't replace a full test suite, but it covers exactly the cases that tend to hide bugs: removing a node with two children, removing a leaf, and verifying that the in-order traversal remains sorted after every change. If these three tests pass after any modification you make to the code, you have a good guarantee that the tree's core property remains intact. ## Where this is used in real life It's worth understanding that this isn't an academic structure with no practical application. Database indexes use variants of search trees (usually B-Trees, a generalization for disk storage) to locate records quickly. Autocomplete features and sorted suggestion lists in applications use trees to keep datasets always searchable and ordered. File systems organize directories hierarchically with similar properties. And whenever you need a structure that keeps data sorted while allowing efficient insertions and removals, the family of binary search trees — from the simple version to its balanced variants — tends to be the answer. ## Next steps If you've made it this far and implemented all of this yourself, you already understand recursion, references, and algorithmic complexity far better than most people who've only read about it. The natural next step is to tackle the imbalance problem head-on: implement an AVL tree, which adds rotations to insertion and deletion to keep the tree always balanced, or try applying this simple BST to a real problem — a searchable dictionary, an autocomplete system, or an index for a small search engine. It's in that kind of practical application that the structure stops being an exercise and becomes a tool.