Trees

Keeping records out of interior nodes lets each interior page hold only separator keys and pointers, raising fanout and lowering height. Linking the leaves turns a range scan into one descent plus a sequential walk instead of a tree traversal.

In a Fenwick tree, node i aggregates the lowbit(i) positions ending at i. Stripping that low bit lands on the last position the node did not cover, so successive nodes tile the prefix with no gap and no overlap.

The LCP array records how many leading characters each adjacent pair of lexicographically sorted suffixes shares. The largest entry is the length of the longest segment occurring at least twice, and the offset beside it says where that segment starts.

A suffix array holds n integers: the starting positions of a text's n suffixes, sorted in lexicographic order. The suffixes themselves are never copied — each is read from the original text — so the space stays O(n).

A trie saves memory only when keys share long prefixes. For long, mostly distinct keys it allocates about one node per symbol, each with child links and a marker — usually far more than storing the keys whole in a hash set.

Worst case O(n^2): each node's height is recomputed once per ancestor, so a chain-shaped tree pays the sum of all depths. A balanced tree costs O(n log n). Fusing both walks into one post-order pass restores O(n).

The recursion seeded its initial bounds with the key type's extreme representable values, so a real key equal to that extreme is indistinguishable from being out of range. Make the bounds optional and skip absent comparisons, or use a bound type wider than the key type.

Usually yes: the strict invariant charges constant restructuring per write and buys a worst-case height near 1.44·log2(n) on every read, so at a thousand reads per write the shorter search paths dominate. Confirm by measuring at production size.

Red-black trees pay less per write: at most two rotations per insertion, three per deletion, and the common repair changes colors only. AVL rebalancing after a deletion can rotate all the way to the root. AVL's tighter height wins when reads dominate.

You take over the bookkeeping recursion did for you. An explicit stack holds pending nodes, and children are pushed in reverse so the left pops first. Preorder converts mechanically; postorder needs extra state to know both children finished.

Flag that the arrival order is sorted: every key lands to the right of the previous one, so the index becomes a chain of length n. Lookups degrade from O(log n) to O(n), and the import loop itself costs Θ(n²).

Carry a candidate down the ordinary search descent: when the current key is below X, record it and step right; when it is above X, step left. The last recorded key is the largest at or below X.

A Fenwick tree answers a general range by subtracting prefixes, which requires an invertible aggregate. Minimum has no inverse — two prefix minima say nothing about the range between them — so range minima need a structure that combines covering blocks.

A hash structure answers exact-key membership only, and a destination address is almost never itself a stored entry. Longest-prefix match asks which stored prefix of any length matches deepest — that needs an ordered descent, not one lookup.

Usually yes: past a few dozen queries the one-time build amortises, while a per-query scan never stops costing. Decide on resident memory — roughly four bytes per character plus the archive — how often the archive changes, and who will own the index.

Measure first: node count, fanout and bytes per node. The usual culprit is a child slot reserved per possible symbol — fine for a tiny alphabet, impossible for a universal one. The levers: children representation, compression, byte indexing, or no trie at all.

The uncle's color decides. In a red-black tree insert fixup, a red uncle means recolor parent, uncle and grandparent and push the violation two levels up; a black or absent uncle means one or two rotations end the repair immediately.

It corresponds exactly to preorder on the original n-ary tree. Left-child right-sibling gives every node two fixed pointers, first child and next sibling, and a preorder walk of that binary shape emits the original nodes in the original order.

A newly posted reply is always a leaf, so its height is zero no matter how deeply it sits. The rule needs depth, the distance from the thread root, which is the parent's depth plus one and is known at insertion.

Not at the same node size. High fanout was never valuable in itself — it matched node size to the storage transfer unit. In memory that unit shrinks from a page to a cache line, so the right node holds tens of keys, not hundreds.

Suffix arrays win on constants, not asymptotics. A suffix tree costs roughly ten to twenty bytes per character in nodes and pointers; a suffix array is one integer per position, is far friendlier to caches, and with an LCP array it answers most of the same queries.

When queries are frequent, the tree is deep, and mutations are rare or append-only. An index buys O(log n) queries for O(n log n) build time and memory, and re-parenting invalidates it. On a shallow or churning tree the walk wins.

Preserve the shape whenever the shape is semantic: evaluation order, branch identity, per-node metadata, or paths that appear in audit records. When the tree is merely an ordered index over keys, ship the keys in order and let the receiver rebuild — smaller, self-checkable and far more tolerant of version skew.

Put the guarantee in the structure, not in caller discipline: a shared index whose inputs you do not control should maintain its own height bound. Caller-side fixes fit only small, bounded, cold indexes.

Decide from the aggregate and the workload, not from elegance: the compact prefix-based structure fits only invertible aggregates, a segment tree fits any associative one, and batched writes justify neither.