Trees

What is a Tree

A tree is a set of nodes where every node has exactly one parent — except one, the root, which has none. That single constraint is the whole definition. Every other word in this article is a consequence of it.

It is worth noticing what that rules out. No node can have two parents, so nothing is reachable by two different routes. No node can be its own ancestor, so following the structure downward always terminates. A tree is what you get when you take the idea of nodes pointing at nodes and forbid it from ever looping back.

Trees are drawn upside down, root at the top, and nobody has ever fixed this. Read "down" as "away from the root" and the vocabulary stops fighting the picture.

The problem previous structures couldn't solve

Every structure so far stores values in some arrangement. What none of them can store is hierarchy — the fact that one thing contains, owns, or precedes several others.

Arrays give you position. Position is a relationship, but a flat one: element 4 sits beside element 5 and that is all it can ever mean. There is no way for element 4 to contain elements 7 through 12.

Linked lists give you succession — a node pointing at the node after it. That is genuinely a relationship between nodes, and it is the right shape for this article to build on. But it is exactly one next per node, so a linked list can only ever express a line.

Hash tables give you key → value in O(1). Fast, and hierarchy-blind: the whole point of a hash function is to scatter keys, which destroys any relationship between them.

What all three are missing is one-to-many. A directory holds many files. An HTML element wraps many elements. A manager has many reports, each of whom may have reports of their own. Change the linked list's single next into a list of children and you have a tree — which is why this is the article that comes after that one.

The vocabulary

Trees carry more terminology than any structure so far, and most readers meet it as a wall of definitions. It is smaller than it looks: every term below names a position in the same picture, so it is easier to keep one tree on screen and point at it.

Root, parent, child, sibling, leaf

• Root — the one node with no parent. A tree has exactly one, and it is your only way in.
• Parent and child — the two ends of an edge. Every node except the root has exactly one parent, and any number of children.
• Siblings — nodes sharing a parent. Note there is no edge between them; siblings are related by where they sit, not by a pointer.
• Leaf — a node with no children. This is where the structure stops.
• Internal node — a node with at least one child. Every node is either a leaf or internal, never both.
• Ancestor and descendant — the transitive versions. Your parent's parent is an ancestor; every node below you is a descendant.

Subtree

A subtree is any node together with all of its descendants. The tree in the figure above has a subtree rooted at b containing b, e and f.

This is the most useful idea in the vocabulary, because it is what makes recursion work. "Sum every value in this tree" is not a problem you solve by walking a loop; it is value + sum of each child's subtree, and each of those is the same problem on something smaller. Once you see subtrees, most tree code writes itself.

A forest is a set of trees with no root joining them — what you have left if you delete a root and keep its children.

Depth and height

These two get conflated constantly, and the confusion is worth spending a figure on. Both count edges; they count from opposite ends.

Depth is a property of a node: how many edges lie between it and the root. The root has depth 0.

Height is a property of a subtree: the number of edges on the longest path from that node down to a leaf. Every leaf has height 0, and the height of a tree means the height of its root.

A level is the set of all nodes at one depth. Level 0 is the root by itself.

Height is the number that matters for performance, and it is the number every later article in this series is really about. Depth tells you where a node sits. Height tells you the worst case for reaching one — because the longest root-to-leaf path is how much work a search can be forced to do.

A tree has exactly V − 1 edges

Count the nodes in any tree, subtract one, and you have the number of edges. The figure above has seven nodes and six edges.

The reason is the definition, restated: every node has exactly one parent except the root, and every edge is precisely one node's link to its parent. So edges and non-root nodes are the same collection counted two ways.

This is a genuinely useful invariant, not trivia. It means a tree is the sparsest structure that can still connect everything — remove any edge and it falls into two pieces, add any edge and you create a cycle and it stops being a tree.

Representing a Tree in memory

The definition says each node has a value and some children. The only real decision is how to store "some children".

The direct approach gives every node a slice of child pointers. It reads exactly like the definition, and it is what you should reach for by default.

Notice that Height returns 0 for a leaf without a special case for it: the loop simply does not run. Tree code is full of base cases that arrive for free like this, which is most of why it stays short.

First child, next sibling

There is a second representation worth knowing, because it turns up in real systems and because of what it is made of.

Instead of a slice per node, give every node two pointers: one to its first child, and one to its next sibling.

That is a linked list hiding inside a tree. A node's children are not stored as a collection at all — they are a chain, and the parent only holds the head of it. Walking them is the traversal loop from the linked lists article, unchanged:

The payoff is a fixed node size. Every node is exactly two pointers wide no matter how many children it has, with no slice header and no reallocation when a child is appended — which is why it shows up in memory-constrained places and in compilers, where node counts are enormous and the tree is built once and then only read.

The cost is that the slice representation's cheap operations become linear. "How many children does this node have" is a walk. "Give me the third child" is a walk. You have traded indexed access for a smaller, stabler node — the same trade the linked lists article made, appearing one level up.

Try it yourself

You've seen the vocabulary and both representations — now build some trees and watch two things hold no matter what you do. Every tree has exactly one edge fewer than it has nodes, and no node can appear without its parent, because there would be nothing to attach it to.

Common operations and their costs

For the slice representation, where n is the number of nodes and h the height:

The pattern is that structural edits are O(1) and questions about content are O(n). That should look familiar — it is the linked list's profile, because a tree is built the same way. And it is the reason the next articles exist: a plain tree gives you no way to search faster than checking everything. Every remaining article in this series is about adding a rule to the tree that turns O(n) searching into O(h), and then making sure h stays small.

Trees in the real world

Filesystems

The example that needs no translation. Directories are internal nodes, files are leaves, and / is the root. Note where reality bends the rules: a hard link gives a file two parents, and a symlink can point anywhere at all, including upward. Both are deliberate escapes from tree-ness, and both are why find has to worry about loops.

The DOM

An HTML document is a tree, and the browser hands it to you as one. parentNode, childNodes, firstChild — the vocabulary in this article is the API. CSS selectors are queries over that tree, and the reason .a .b is slower than .b is that it has to walk ancestors.

Configuration and data interchange

JSON, YAML and TOML are all tree serializations. An object is an internal node, a scalar is a leaf, and nesting is the parent-child edge. This is why every config format has an unambiguous path syntax — .spec.containers[0].image is a route down from the root.

Compilers

Source code is parsed into an abstract syntax tree, where an expression's operator is the parent of its operands. 2 * (3 + 4) becomes a * node whose children are 2 and a + node. Evaluating it is a post-order walk, which the traversals article covers directly.

Organizational and category hierarchies

Org charts, taxonomies, product categories, comment threads, routing tables. Any time a thing belongs to exactly one bigger thing, the natural model is a tree — and the natural database representation is a parent_id column, which is the parent-pointer representation stored in a table.

When Trees fall short

One parent is a real constraint. It is the source of everything convenient about trees, and it is a modelling limit. Tagging, social connections, many-to-many relationships of any kind — none of them fit, and forcing them into a tree means duplicating nodes or inventing a second structure alongside it.

Height is not guaranteed to be small. Nothing in the definition says a tree is bushy. A tree where every node has exactly one child is a linked list wearing a different type, with height n − 1 instead of log n, and every operation that was supposed to be cheap is linear. This failure mode is the entire reason the balanced-trees article exists.

Depth costs stack. Recursive tree code is short because the call stack does the bookkeeping, but that stack is finite. A tree deep enough will overflow it, and "deep enough" arrives sooner than you would like on degenerate input — which is why the traversals article spends time on the iterative versions.

Pointer chasing is cache-hostile. Nodes are separate heap allocations, so walking a tree is a sequence of potential cache misses, exactly as it is in a linked list. This is why performance-critical trees get flattened into arrays, a trick the next article introduces and the heap article never stops using.

Something flatter often fits. If the only question you ever ask is "what is this node's parent", a hash table of child → parent answers it in O(1) and needs none of this. If you only ever iterate everything in order, a slice is faster. Reach for a tree when the hierarchy itself is what you need to query — not merely because your data happens to be nested.

Summary

Trees are the first structure in this series that is not a line:

• One parent per node, one root, no cycles — the whole definition, and every other property follows from it
• Depth is where a node sits, height is how far it can force you to walk — height is the number that governs performance
• V − 1 edges, always — the sparsest structure that still connects everything
• A subtree is a tree — which is why nearly all tree code is recursive, and why it is so short
• Children as a slice, or first-child/next-sibling — indexed access against a fixed node size, the same trade linked lists made
• Structural edits are O(1), content questions are O(n) — a plain tree gives you no way to search faster than checking everything

The key insight is that trees add hierarchy but not yet order. Nothing here tells you where to look for a value, so finding one still means visiting every node — a tree by itself buys you structure, not speed.

That is what the rest of this series is about. Constrain a tree to two children and the shape becomes something you can reason about arithmetically; add a rule about which child a value belongs in and searching drops to the height of the tree; then keep the height small and that becomes a guarantee. The next article takes the first of those steps.