#trees
11 articles
Trees: When Data Branches
Move beyond flat lists and discover why trees power everything from file systems to databases. Learn nodes, roots, leaves, height, and how a balanced tree buys you O(log n) on a silver platter.
Union-Find (Disjoint Set Union)
The near-magic data structure for connectivity queries — are these two nodes in the same component? Nearly O(1) per operation with union by rank and path compression. Kruskal's MST, redundant connections, account merging, and more.
Tries (Prefix Trees)
The data structure powering autocomplete, spell-check, and IP routing — a tree where each edge is a character and every path from the root spells a prefix. Insert, search, and prefix queries all run in O(L) on word length alone, completely independent of how many words you store.
Segment Trees
Segment trees answer range queries AND handle point or range updates in O(log n) — the structure to reach for when prefix sums aren't enough and you need both reads and writes at scale.
Fenwick Trees (Binary Indexed Trees)
Fenwick trees give you O(log n) prefix-sum queries AND point updates in ~10 lines of code — leaner and faster in practice than a segment tree for this exact job. Learn the lowbit trick, build the tree, and know when a BIT beats everything else.
Balanced BSTs (AVL & Red-Black Trees)
Self-balancing trees fix the degenerate-BST problem by keeping height O(log n) guaranteed — which is why Java's TreeMap, C++'s std::map, and every ordered set in the standard library runs on one under the hood.
Heaps and Priority Queues
The heap data structure gives you O(1) peek at the min (or max) and O(log n) insert and extract — the exact shape you need for scheduling, K-way merging, and the top-K pattern that shows up everywhere in systems interviews.
Binary Trees and Traversals
Master binary tree traversal — inorder, preorder, postorder, and level-order — and the recursive mindset that makes dozens of tree problems click instantly.
Binary Search Trees
The left<node<right invariant gives you O(log n) search, insert, and delete — until the tree degenerates into a linked list. Here's the full picture, including why inorder traversal is a free sort.
DFS Patterns
Depth-first search is the backbone of cycle detection, flood fill, path enumeration, and clone graph — master the visited-set template, the 3-color trick, and when to reach for DFS over BFS.
BFS Patterns
Queue-driven level-by-level traversal and why breadth-first search is the only guaranteed way to find shortest paths in unweighted graphs. Templates, traps, and four worked problems.