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

Problem Context

Trees are the data structure that quietly underpin most of computing — file systems, DOM, B-trees in every database engine, syntax trees in every compiler, decision trees in classical ML, and the JSON document you parsed five minutes ago. The shape decides almost everything about the cost: a balanced binary tree gives O(log n) operations; the same data inserted in sorted order into a naive BST collapses to a linked list with O(n) operations.

This guide is the practical tree mental model in 2026 — when to reach for which kind, when the BCL gives you a self-balancing tree for free, and when you genuinely need to roll your own (rarely).

Concept Explanation

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

Implementation

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;
}

Pitfalls

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.

Practical Takeaways

• 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.