Trees in the Wild

Nothing on this page is needed for an interview. It exists because knowing that git status is fast for the same reason a segment tree is fast makes both of those ideas stick in a way another practice problem does not.

1. The map

System	The tree is	Why that shape
Filesystems	directories and the files/directories inside them	One parent per entry keeps 'where is this file' unambiguous - until hard links break it. Section 2.
The DOM	HTML elements, nested by markup	Nesting is containment, so layout, painting and event bubbling all walk the same tree.
Compilers	an AST, expressions nested by precedence	Deeper nesting binds tighter; the shape of the tree encodes the order of operations. Section 2.
B+ trees (databases, filesystems)	a wide, shallow search tree with data only in the leaves	Minimises disk reads: every leaf is the same depth, and each read pulls in a whole page. Section 3.
LSM trees (write-heavy databases)	a chain of progressively larger sorted trees, merged over time	Turns random writes into sequential ones; reads pay for it later. Section 3.
Git	commits, trees and blobs, addressed by content hash	Unchanged content is provably the same object, so most of the tree does not need to be touched or resent. Section 4.
Decision trees / gradient boosting	a tree of learned yes/no splits over feature values	Each split is a greedy, locally-optimal partition of the data - the tree is the model.
A heap, as an array	a complete binary tree, stored with a node's children at 2i+1/2i+2	No pointers to store or chase - the shape is implicit in the index arithmetic.
Union-find	a forest of parent pointers, flattened almost flat by path compression	Barely a tree at all by the time it is fast - see section 5.
Huffman coding / a trie	a binary tree of prefix codes, or a tree of shared string prefixes	A root-to-leaf path is a code or a word, and shared prefixes are shared paths - the whole point is that structure IS the data.

2. Filesystems, the DOM, and parse trees

A filesystem directory tree is the most literal tree most people use daily: a folder contains files and other folders, and each entry has exactly one parent. That last clause is the one that is not quite true.

A hard link is a second directory entry pointing at the same underlying file (the same inode), not a copy. The moment two names point at one file, the filesystem is no longer a tree - it is a DAG, because that one file now has two parents.

report.txt has two parents - /docs/final.txt and /archive/2024/report.txt both point at it. Deleting either name leaves the file alive; the file is only freed when its last name is removed.

⚠

A recursive directory walk assumes a tree

A naive recursive directory walk (os.walk, a hand-rolled DFS) assumes every node has exactly one parent, which a hard link violates and a symlink loop violates worse. A symlink pointing back at an ancestor directory turns the walk into an infinite recursion, not just a double-count - the same "parent-skip" problem that shows up walking an undirected graph as if it were rooted. Real tools track visited inodes for exactly this reason.

The DOM stays a genuine tree - every element has exactly one parent, full stop - and that is what makes CSS layout a post-order pass: a container cannot know its own size until every child has already reported its size, the same "answer flows up from the leaves" shape as computing a tree's height. Painting, by contrast, is naturally pre-order: a parent's background has to be drawn before its children sit on top of it. One tree, two different traversal orders, because the two questions ("how big am I" vs "what draws over what") need answers flowing in opposite directions.

A parser's output - the AST - encodes operator precedence as nesting depth, not as anything explicit. 2 + 3 * 4 parses to + at the root with 3 * 4 as its right child, precisely because multiplication binds tighter and therefore sits deeper. Evaluating the tree bottom-up (post-order) automatically respects precedence without ever consulting a precedence table again - the table did its job once, at parse time, by shaping the tree.

3. Databases: B+ trees and LSM trees

A B+ tree is the index structure behind most relational databases and filesystems (MySQL's InnoDB, most of ext4). Two decisions distinguish it from the balanced binary trees covered elsewhere on this track:

• All the data lives in the leaves. Internal nodes hold only routing keys
  • copies used to decide which child to descend into - never the record itself.
• The leaves are linked to each other, left to right, forming a sorted chain.
• Nodes are wide - hundreds of keys per node, not two - sized to exactly one disk page.

	Balanced BST (AVL / red-black)	B+ tree
Branching factor	2	hundreds, sized to a disk page
Where data lives	any node	leaves only
Height for 1M records	~20	~3
Range scan	in-order traversal, following child pointers	walk the leaf chain directly - no tree involved
Optimised for	CPU cache, in-memory comparisons	minimising disk reads (each node read is one page fault)

A B+ tree's whole design optimises for one number: disk reads per query.

Every internal node fits in exactly one page, so descending one level costs exactly one disk read (or one cache line, further up the memory hierarchy). Making the tree as wide as possible is the same move as making it as shallow as possible - and the linked leaves turn "give me everything between these two keys" into a scan with zero extra tree lookups after finding the start.

LSM trees (log-structured merge trees - Cassandra, RocksDB, most modern write-heavy stores) invert the B+ tree's tradeoff on purpose. Writes never touch a sorted structure on disk directly: they land in an in-memory table, and once that fills, the whole thing is flushed as one new sorted file. Reads have to check several of these files, newest first, and a background process periodically merges them back down.

	B+ tree	LSM tree
A write is	an in-place update, somewhere inside the tree	an append - always sequential
A read checks	one tree	the in-memory table, then progressively older files, newest first
Best for	read-heavy, in-place-update workloads	write-heavy workloads, especially at high throughput
The cost deferred	none - the tree stays sorted at all times	compaction - merging old files back down, later, in the background

Mnemonic

B+ trees keep the structure sorted at write time; LSM trees keep it sorted at read time. Every write to a B+ tree pays the cost of staying sorted immediately - find the leaf, maybe split a page. Every write to an LSM tree defers that cost: append now, and let a background compaction pass do the sorting work later, amortised over many writes at once.

4. Git: a Merkle tree you use every day

Every Git object - a blob (file contents), a tree (a directory listing), a commit - is named by the SHA-1 (or SHA-256, in newer repos) hash of its own content, including the hashes of the objects it points to. That is a Merkle tree: a tree where every node's identity is derived from what is underneath it.

Content addressing - naming an object by the hash of its content - is what makes this cheap. Two files with identical bytes are, provably and for free, the same blob object, no comparison needed beyond comparing two hashes. An unchanged subtree of the directory structure hashes to the same tree object it always did, so Git never has to re-walk it, re-hash it, or re-send it - it is already there, byte-identical, under the same name.

That is the direct answer to two things that otherwise look unrelated:

• Why git status is fast. It does not diff file contents; it compares hashes it already has, most of which are unchanged, so most of the comparison is O(1) hash equality rather than a byte-by-byte scan.
• Why a commit hash pins the whole history. A commit's hash is a function of its tree's hash and its parent commit's hash, which is a function of its tree and its parent - all the way back to the first commit. Changing one byte anywhere in that history changes every hash after it, which is exactly the property that makes a commit hash a tamper-evident pointer to everything before it.

A git commit --amend does not edit anything - it creates an entirely new object and abandons the old one. Because objects are content-addressed and therefore immutable (changing the content would just produce a different hash, not modify the existing one), there is no such operation as "mutate a commit." amend builds a new commit object with the new content, points the branch reference at it, and the old commit becomes unreachable garbage, eventually collected. Rebasing is the same idea repeated: replay each commit in topological order, producing all-new objects with all-new hashes.

5. Trees that are not made of pointers

"Tree" is a shape, not an implementation. Several structures earlier on this track are trees with no .left/.right fields anywhere in sight:

Structure	The tree it is	Why the pointer-free form
A binary heap	a complete binary tree	index 2i+1/2i+2 IS the child relationship - completeness (no gaps) is exactly what makes the array packing waste zero slots. See Heaps.
A segment tree	a balanced binary tree over array indices	same array trick as a heap - node i's children are 2i+1 and 2i+2. See Range Query Trees.
Union-find	a forest, one parent-pointer array deep	path compression flattens each tree toward a star on every find, so 'the tree' barely resembles one after enough operations - it is a tree in the sense that a DAG is briefly a tree before compression, not a fixed shape you traverse.
A trie	a tree of shared string prefixes, one node per prefix	a root-to-node path spells out a prefix; two words sharing a prefix literally share that path, which is the whole reason a trie beats a hash set for prefix queries.
Huffman coding	a binary tree built bottom-up by repeatedly merging the two rarest symbols	a root-to-leaf path IS the code for that symbol, and shorter paths are given to more frequent symbols - the tree's shape is the compression.
Decision trees / gradient boosting	a tree of learned yes/no splits over feature values	each split greedily partitions the training data; a boosted model is a sum of many small trees, each correcting the previous ones' errors.

Whenever an index formula, a parent array, or a path-encodes-meaning trick replaces .left/.right, ask what property of "tree" is actually being used

• is it the recursive decomposition (subtrees are trees), the unique root-to- node path, or just the acyclic connectivity? Usually only one of those three is load-bearing, and the pointer-free version keeps exactly that one and throws the rest away for speed or memory.

Where to go next

• Tree Anatomy - back to the vocabulary, if a term above (subtree, root, forest) was unfamiliar.
• Range Query Trees - the segment tree and Fenwick tree referenced in section 5, worked in full.
• Heaps - the array-packed complete binary tree from section 5, with the sift-up/sift-down operations that keep it valid.
• Balanced Trees - the in-memory cousin of the B+ tree from section 3, minus the disk-page sizing.