Red-black trees, B-trees in DB, PriorityQueue, prefix queries.

Trees — BSTs, Heaps, Tries, Iterative Traversal

Trees model hierarchical relationships. BSTs support O(log n) search/insert/delete when balanced. Self-balancing trees (red-black, AVL) maintain balance automatically. .NET's SortedDictionary is a red-black tree. B-trees power database indexes. Heaps (max/min) support O(log n) priority queue operations — .NET's PriorityQueue<T> is a min-heap. Tries index string data for O(m) prefix lookups. All tree traversals can be made iterative with explicit Stack<T>.

Interactive Pipeline Flow

UnderstandImplementOptimise

🌳 BST — insert/search O(log n)

BST property: left subtree values < node < right subtree. Unbalanced BSTs degrade to O(n) on sorted input.

Architecture Diagrams

Tree traversal order and when to use each.

Loading diagram...

Key Design Decisions

🌳SortedDictionary is O(log n), not O(1)

SortedDictionary<K,V> is a red-black tree. Perfect for ordered iteration but slower than Dictionary<K,V> for point lookups.

🔤Trie for autocomplete and prefix problems

For "find all words starting with 'pre'" queries, a Trie is O(m) where m is the prefix length. A sorted list requires O(m·log n).

🔄Iterative traversal for production code

Any tree traversal on user-controlled data (file system, JSON) must be iterative with explicit Stack<T> to avoid StackOverflowException.

Discussion