The first time I had to write a tree from scratch in production was a permissions system that needed to model an organization hierarchy. I had read about trees in a textbook, written one in CS class, and forgotten everything except the word "recursion". A senior engineer let me try the naive version. It worked beautifully on test data, then exploded on the production payload because every insert hit a worst-case path. He sat down with me, drew a few diagrams on a whiteboard, and walked me through why a balanced tree was different from the thing I had built. That afternoon is the reason I take trees seriously.

This article is the version of that whiteboard session, with the math kept light and the tradeoffs called out honestly. By the end of it you should know what trees buy you over arrays and hash tables, why a plain Binary Search Tree is almost never the right production choice, and which balanced variants people actually run.

What a tree is, and why it shows up everywhere

A tree is a hierarchy of nodes, each pointing to zero or more children, with no cycles. There is exactly one node with no parent (the root). If you draw a family tree, a file system, an HTML DOM, a React component tree, or the output of git log --graph, you are drawing a tree.

The operations you typically want on a tree are: insert a node, find a node, remove a node, traverse the structure in some order. The cost of each operation depends on the tree's height. For a balanced tree of n nodes, height is O(log n). For an unbalanced tree, height can be as bad as O(n). The whole engineering art of working with trees is about keeping the height close to logarithmic.

Binary Search Trees: the elegant idea that fails alone

A Binary Search Tree (BST) is a binary tree (each node has at most two children) where every left descendant is less than the node and every right descendant is greater. That ordering invariant makes lookup, insert, and delete O(h) where h is the height of the tree.

class BSTNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

function insert(node, value) {
    if (!node) return new BSTNode(value);
    if (value < node.value) node.left = insert(node.left, value);
    else if (value > node.value) node.right = insert(node.right, value);
    return node;
}

The code is short and clean. The problem is that the tree's shape depends on insertion order. Insert [1, 2, 3, 4, 5] in order and you get a tree that is just a right-only chain (1 -> 2 -> 3 -> 4 -> 5). Lookup is O(n), the same as a linked list. The asymptotic advantage you bought is gone.

Insert [3, 1, 4, 1, 5, 9, 2, 6]:

            3
           / \
          1   4
               \
                5
               / \
              ...   9
                   ...

Insert [1, 2, 3, 4, 5, 9]:

        1
         \
          2
           \
            3
             \
              4
               \
                5
                 \
                  9

A balanced BST keeps h = O(log n) even on adversarial input. A naive BST does not. Production systems handle adversarial input. So production systems use balanced BSTs.

Tree traversals: the four orders that matter

Before I move on to balanced variants, the four standard traversals show up in interviews and in real code, so they are worth naming. All four take O(n) and use either recursion (clean, with a O(h) call stack) or an explicit stack/queue (iterative, same big-O).

The in-order traversal of a BST visits nodes in sorted order. That is the one property that makes BSTs useful as more than just lookup tables. A hash table can give you O(1) lookup, but cannot give you sorted iteration without a separate sort. A BST gives you both.

The balanced variants that actually run in production

There are four self-balancing binary search trees you will run into in real systems. They all maintain O(log n) height by rebalancing on insert and delete.

AVL trees. The strictest balance: heights of left and right subtrees differ by at most 1. Lookups are very fast. Inserts and deletes can trigger several rotations. AVL is great when reads dominate writes.

Red-Black trees. Looser balance than AVL: the longest path is at most twice the shortest. Inserts and deletes are faster than AVL because they need fewer rotations on average. This is the workhorse. Java's TreeMap and TreeSet use it. The Linux kernel scheduler uses a red-black tree for run-queue ordering. C++'s std::map and std::set use it.

B-trees and B+ trees. Multi-way trees (each node has many children, typically 100+ on disk). Designed for systems where reading a node is expensive (disk, SSD, network) so you want to minimize tree height. Every relational database (PostgreSQL, MySQL, SQL Server, Oracle) uses a B+ tree as its primary index structure.

Treaps and Splay trees. Randomized or self-adjusting variants. Treaps are simple to implement, splay trees adapt to access patterns. They are common in competitive programming and rarer in production.

The practical takeaway: when you reach for an ordered-map or an ordered-set in any standard library, you are getting a balanced BST under the hood. You almost never write the balancing code yourself. You read CLRS chapter 13 once to understand why it works, and then you trust the library.

Insert, in code, with the balance handwave

A full red-black insert is about 100 lines of careful pointer work. I am not going to write it here, but I want to show what the unbalanced version looks like and call out where the balance step would slot in.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    elif value > root.value:
        root.right = insert(root.right, value)
    # In a balanced tree, this is where you'd:
    # 1. Update height / color of `root`
    # 2. Detect imbalance via balance factor or red-violation
    # 3. Apply zero, one, or two rotations to restore balance
    return root

The interesting work in any balanced BST is concentrated in those three commented lines. Every variant (AVL, red-black, AA-tree) defines them differently. Read one implementation carefully and the others click into place.

When NOT to use a tree

Three cases where I have explicitly chosen something else.

First, when you only need lookup and never need ordering, a hash table is faster (O(1) average) and uses less memory per entry. The only reason to pick a tree over a hash table is that you need ordered iteration, range queries, or predictable worst-case lookup time.

Second, when keys are short strings with shared prefixes, a trie beats a BST. Trie lookup is O(k) where k is the key length, regardless of how many keys you have.

Third, when the data set is small (say, under a few hundred items) and access patterns are simple, a sorted array with binary search is often faster than a balanced BST in practice, because it is cache-friendly and has no per-node pointer overhead.

Where this fits in 2026

Most product engineers I work with go years without writing tree-rebalancing code by hand. The balanced trees they touch live inside their database, inside their language's standard library, or inside an in-memory cache they did not write. That is fine. You should still understand the structure, because three things have not changed and will not.

First, the worst-case-vs-average distinction matters more, not less, as systems get bigger. A naive BST that works on test data and degrades on production data is the same shape of failure as a naive hash table that gets attacked. Knowing which structure you imported from the standard library, and what its worst-case bound is, is part of the job.

Second, hierarchical data is everywhere. ASTs in compilers, DOM in browsers, comment threads, file systems, route trees in Next.js, component trees in React, decision trees in ML, scene graphs in games, configuration trees in Kubernetes. The list does not get shorter. The traversals you learned for BSTs are exactly the traversals you use for all of them.

Third, B-trees and B+ trees inside databases are about to get more interesting, not less. Storage tiers are stratifying (NVMe, persistent memory, fast network storage), and the B-tree variants that perform well on each tier are an active area of database research. If you ever maintain a database, knowing why a B+ tree beats a B-tree for range scans, and why an LSM-tree beats both for write-heavy workloads, will save you. The textbook BST is a teaching device. The thing you actually run is one of its descendants. Learn enough of the family to recognize which one you are touching.