Trees: BSTs, Balance, and Why SortedDictionary Is Red-Black

The Shape of the Tree Decides the Cost

A search box suggested product names by scanning half a million names on every keystroke. The first fix was a hand-written binary search tree, loaded from a file that happened to be sorted. Every node got only a right child, and the “tree” became a linked list that was slower than the scan it replaced.

Trees are everywhere: file systems, the DOM, every database index, every parsed document. Their cost depends almost entirely on shape. Balanced trees give logarithmic operations; unbalanced ones can degrade to linear. Below is which tree to use for which question, what your standard library already gives you, and when a trie or the database's B-tree is the better answer.

BSTs, Balanced Trees, Heaps and Tries

Five families cover almost every real-world need:

• Binary Search Tree (BST)— left < node < right. O(log n) when balanced, O(n) when not. Don't use a plain BST in production.
• Self-balancing BST (Red-Black, AVL) — guaranteed O(log n) operations. SortedDictionary<K,V>and SortedSet<T> in .NET are red-black.
• B-tree / B+tree — high fan-out (hundreds of children per node), tuned for disk/SSD pages. The structure inside every relational database index.
• Heap — partially ordered tree (parent ≤ children for min-heap). O(log n) push/pop, O(1) peek. .NET 6 shipsPriorityQueue<TElement, TPriority> as a min-heap.
• Trie / Prefix tree — one node per character; great for autocomplete, IP routing, dictionary-based string matching.

flowchart LR
    P["Need a tree?"] --> Q1{"Need ordered<br/>iteration / range?"}
    Q1 -->|no| H{"Need top-K /<br/>priority?"}
    H -->|yes| HEAP["PriorityQueue&lt;T,P&gt;<br/>(min-heap)"]
    H -->|no| HASH["Dictionary&lt;K,V&gt;<br/>(hash, not a tree)"]
    Q1 -->|yes| Q2{"Prefix queries?"}
    Q2 -->|yes| TRIE["Trie<br/>(roll your own)"]
    Q2 -->|no| Q3{"On disk /<br/>huge dataset?"}
    Q3 -->|yes| BTREE["B-tree<br/>(use a real DB index)"]
    Q3 -->|no| RB["SortedDictionary / SortedSet<br/>(red-black, in BCL)"]

    style RB fill:#16a34a,color:#fff,stroke:#15803d
    style HEAP fill:#0078D4,color:#fff,stroke:#005a9e

Using and Walking Trees in Real Code

Step 1: 90% of the time — use the BCL

// Self-balancing ordered map: O(log n) for all ops, ordered iteration
var byTime = new SortedDictionary<DateTime, Order>();
byTime.Add(DateTime.UtcNow, order);
var firstAfter = byTime.Where(kv => kv.Key > cutoff).First();   // O(log n + k)

// Min-heap (since .NET 6)
var pq = new PriorityQueue<Job, int>();
pq.Enqueue(job, priority: 5);
pq.Enqueue(other, priority: 2);
var next = pq.Dequeue();              // pops job with smallest priority

// Range views (without copying)
var sortedSet = new SortedSet<int>(numbers);
var range = sortedSet.GetViewBetween(10, 20);   // O(log n) + O(k)

Step 2: A real BST node — when you need full control

public class Node<T> where T : IComparable<T>
{
    public T Value;
    public Node<T>? Left, Right;
    public Node(T v) => Value = v;
}

public class BST<T> where T : IComparable<T>
{
    private Node<T>? _root;

    public void Insert(T v) => _root = Insert(_root, v);
    private static Node<T> Insert(Node<T>? n, T v)
    {
        if (n is null) return new Node<T>(v);
        int c = v.CompareTo(n.Value);
        if      (c < 0) n.Left  = Insert(n.Left,  v);
        else if (c > 0) n.Right = Insert(n.Right, v);
        return n;
    }

    public bool Contains(T v)
    {
        var n = _root;
        while (n is not null)
        {
            int c = v.CompareTo(n.Value);
            if (c == 0) return true;
            n = c < 0 ? n.Left : n.Right;
        }
        return false;
    }
}

Step 3: Iterative in-order traversal (no stack overflow)

public static IEnumerable<T> InOrder<T>(Node<T>? root) where T : IComparable<T>
{
    var stack = new Stack<Node<T>>();
    var n = root;
    while (n is not null || stack.Count > 0)
    {
        while (n is not null) { stack.Push(n); n = n.Left; }
        n = stack.Pop();
        yield return n.Value;
        n = n.Right;
    }
}

Step 4: Heap from scratch (when you need a custom comparer)

public class MinHeap<T>
{
    private readonly List<T> _h = new();
    private readonly IComparer<T> _cmp;
    public MinHeap(IComparer<T>? cmp = null) => _cmp = cmp ?? Comparer<T>.Default;
    public int Count => _h.Count;

    public void Push(T v)
    {
        _h.Add(v);
        for (int i = _h.Count - 1; i > 0;)
        {
            int p = (i - 1) / 2;
            if (_cmp.Compare(_h[i], _h[p]) >= 0) break;
            (_h[i], _h[p]) = (_h[p], _h[i]); i = p;
        }
    }

    public T Pop()
    {
        var top = _h[0];
        _h[0] = _h[^1]; _h.RemoveAt(_h.Count - 1);
        for (int i = 0; ;)
        {
            int l = 2*i + 1, r = 2*i + 2, s = i;
            if (l < _h.Count && _cmp.Compare(_h[l], _h[s]) < 0) s = l;
            if (r < _h.Count && _cmp.Compare(_h[r], _h[s]) < 0) s = r;
            if (s == i) break;
            (_h[i], _h[s]) = (_h[s], _h[i]); i = s;
        }
        return top;
    }
}

Step 5: Trie for autocomplete

public class Trie
{
    private class Node
    {
        public Dictionary<char, Node> Next = new();
        public bool IsWord;
    }
    private readonly Node _root = new();

    public void Insert(string s)
    {
        var n = _root;
        foreach (var c in s)
        {
            if (!n.Next.TryGetValue(c, out var nx)) n.Next[c] = nx = new Node();
            n = nx;
        }
        n.IsWord = true;
    }

    public IEnumerable<string> WithPrefix(string prefix)
    {
        var n = _root;
        foreach (var c in prefix)
            if (!n.Next.TryGetValue(c, out n!)) yield break;
        foreach (var w in Collect(n, prefix)) yield return w;
    }

    private static IEnumerable<string> Collect(Node n, string path)
    {
        if (n.IsWord) yield return path;
        foreach (var (c, child) in n.Next)
            foreach (var w in Collect(child, path + c)) yield return w;
    }
}

Step 6: Lowest common ancestor — the canonical interview problem

public static Node<T>? LCA<T>(Node<T>? root, T a, T b) where T : IComparable<T>
{
    var n = root;
    while (n is not null)
    {
        int ca = a.CompareTo(n.Value), cb = b.CompareTo(n.Value);
        if      (ca < 0 && cb < 0) n = n.Left;
        else if (ca > 0 && cb > 0) n = n.Right;
        else return n;     // values split → this is the LCA
    }
    return null;
}

How Trees Go Wrong

1. Plain BST in production. Sorted-input insertion degrades to O(n) per op. Always use a self-balancing tree (SortedDictionary, SortedSet, or implement red-black/AVL).

2. Recursive traversal on adversarial input. A skewed tree of 100k nodes blows the 1MB default stack. Use the iterative Stack<T> traversal for any tree built from untrusted data.

3. Reaching for B-tree in app code. B-trees are a disk-page optimization. In application code with everything in RAM, a red-black tree is faster and simpler. Let the database handle the B-tree.

4. SortedDictionary when you wanted Dictionary. If you don't need ordered iteration or range queries, a hash dictionary is dramatically faster. SortedDictionary trades O(1) lookup for O(log n) ordered operations.

5. PriorityQueue updates aren't supported. .NET's PriorityQueuehas no "decrease-priority" operation. For Dijkstra/A*, the standard trick is to push the new entry and discard stale ones on dequeue (mark-as-visited).

6. Trie memory blowup. A trie over Unicode with millions of words eats hundreds of MB. Use compressed/radix tries (Patricia trie) or just put the dictionary in HashSet<string>if prefix queries aren't the bottleneck.

Which Tree I Would Pick

• Default to SortedDictionary/SortedSet (red-black) and PriorityQueue (heap). Roll your own only when you need a custom invariant.
• Use iterative traversal with Stack<T> for trees built from untrusted input.
• Heaps are O(log n) push/pop, O(1) peek. Use them for top-K, scheduling, Dijkstra/A*.
• Tries shine for prefix queries (autocomplete, IP routing). For pure membership use a hash set.
• B-trees belong in databases, not in application code.
• For Dijkstra-style updates with PriorityQueue, push new entries and skip stale ones — don't try to mutate the heap.
• Always benchmark: red-black tree vs hash dictionary vs sorted array can swap places depending on n and access pattern.