DSA Trees
Trees
A file browser must open /docs/specs/api.md without looping. Folders nest inside folders; each path from the drive root is unique. That hierarchy is a , not an arbitrary web of links.
The power is the property: connected, no cycles, exactly one route from root to each node. Algorithms that assume a parent chain or a clean recursive split rely on that contract.
Algorithm journey
Model the hierarchy
Name a root and parent–child links (or accept a forest of roots).
No cycles; every non-root has exactly one parent.
Measure / size
Walk subtrees once; cost is Θ(n) unless metadata is cached.
Choose representation
Child lists, parent array, first-child/next-sibling, or implicit heap array.
What actually happens
Naive idea: treat the hierarchy like a general graph and BFS everywhere. Correct for reachability, but you pay for cycle checks and lose the “one parent” simplification that makes size, height, and path reconstruction trivial.
Better idea: enforce the tree contract up front. With n nodes there are n − 1 edges. Each child list partitions descendants into disjoint . Recursive queries compose cleanly.
The improved design still fails on a chain of length 10⁵ (recursion depth), on stale parent links after a move, and when “tree” input is actually a DAG or a cyclic graph. Conventions for also disagree across books.
Invariant
The structure stays connected and acyclic with a designated root (or a of roots). Every non-root has exactly one parent; no child link points to an ancestor.
How to choose a tree model
1. Is hierarchy the truth? If cycles or multiple parents are allowed, you need a general graph (or a DAG), not a tree API.
2. Do you walk down, up, or both? Child lists favor descent; a parent array favors ascent; first-child/next-sibling encodes arbitrary arity with two pointers.
3. Is the shape complete? Heaps use an implicit array. Sparse shapes waste space there and belong in linked nodes.
Quantitative check
Size or height on an unindexed tree visits every node: Θ(n). At n = 10⁵, one full walk is fine; nesting that walk inside every mutation is not. A skewed chain has height n − 1, so recursive depth can hit 10⁵ frames and overflow before any answer returns.
The recursive view
A tree is either empty or consists of a root plus zero or more disjoint child subtrees. This definition explains why divide-and-conquer and recursive traversals fit trees naturally.
The graph view
A non-empty tree with n nodes has exactly n − 1 edges. Adding an edge creates a cycle; removing one disconnects the tree. A collection of disconnected trees is a forest.
Interactive tree demo
Use this binary tree as a concrete example of the vocabulary below. Binary trees are one tree family; a general node may have any number of children.
Vocabulary and measurements
| Term | Meaning | Useful consequence |
|---|---|---|
| Root / parent / child | The root has no parent. Every other node has exactly one parent; its outgoing descendants begin with its children. | A node's children define disjoint subtrees. |
| Ancestor / descendant | Ancestors lie on the root-to-node path; descendants lie in the node's subtree. | A node is commonly considered its own ancestor and descendant in inclusive definitions: check the convention. |
| Sibling / degree | Siblings share a parent. A node's degree is its number of children; tree degree is the maximum node degree. | Binary trees have degree at most two. |
| Leaf / internal node | A leaf has no children; an internal node has at least one. | A one-node tree has a root that is also a leaf. |
| Depth / level | Depth is the number of edges from the root. With zero-based levels, level equals depth. | The root has depth 0. |
| Height | A node's height is the longest downward path, in edges, to a leaf. Tree height is root height. | Under the edge convention, a leaf has height 0 and an empty tree has height −1. |
| Size / subtree | Size is the number of nodes. A node together with every descendant forms its rooted subtree. | Subtree sizes support rank and aggregation queries. |
Convention alert: some books count nodes instead of edges, making a leaf's height 1. Both conventions work; state one and use it consistently in formulas and code.
How a tree lives in memory
Child lists
Each node owns a dynamic list of child references. Natural for arbitrary branching; total child references are n − 1.
Parent array
parent[v] identifies a node's parent. Compact and good for upward walks, but discovering children requires an index or a scan.
First-child / next-sibling
Two references encode any rooted tree: one descends to the first child and one moves across siblings.
Implicit array
Position implies relationships. Excellent for complete trees such as heaps, but sparse shapes can waste enormous space.
A general-tree node: size, height, and search
Size and height visit every reachable node, so they take Θ(n) time. Search may stop early but is O(n) in the worst case. Each routine uses an O(h) recursive call stack, which can become O(n) for a chain.
Python
class Node:
def __init__(self, value):
self.value = value
self.children = []
def size(node):
if node is None:
return 0
return 1 + sum(size(child) for child in node.children)
def height(node):
# Edge convention: empty = -1, leaf = 0
if node is None:
return -1
tallest_child = max(
(height(child) for child in node.children),
default=-1
)
return 1 + tallest_child
def contains(node, target):
if node is None:
return False
return (node.value == target or
any(contains(child, target) for child in node.children))Java
import java.util.ArrayList;
import java.util.List;
class Node<T> {
final T value;
final List<Node<T>> children = new ArrayList<>();
Node(T value) {
this.value = value;
}
}
class TreeAlgorithms {
static <T> int size(Node<T> node) {
if (node == null) return 0;
int total = 1;
for (Node<T> child : node.children) total += size(child);
return total;
}
static <T> int height(Node<T> node) {
// Edge convention: empty = -1, leaf = 0
if (node == null) return -1;
int tallestChild = -1;
for (Node<T> child : node.children) {
tallestChild = Math.max(tallestChild, height(child));
}
return 1 + tallestChild;
}
static <T> boolean contains(Node<T> node, T target) {
if (node == null) return false;
if (java.util.Objects.equals(node.value, target)) return true;
for (Node<T> child : node.children) {
if (contains(child, target)) return true;
}
return false;
}
}Cost depends on the question and the stored metadata
| Operation | Typical cost | Why |
|---|---|---|
| Visit every node | Θ(n) | DFS and BFS process each node and edge once. |
| Find an arbitrary value | O(n) | A generic tree has no ordering to prune the search. |
| Walk to root | O(depth) | Requires parent references or a recorded path. |
| Read cached size or height | O(1) | Updates must then repair metadata along affected ancestors. |
| Insert a known child | O(1) amortized | With a dynamic child list; finding its parent may still cost O(n). |
Invariants worth defending
- The root has no parent; every other reachable node has exactly one.
- No child link points to an ancestor, which would create a cycle.
- If parent links exist,
child.parentagrees with the parent's child collection. - Cached size, height, or aggregate values are updated after every mutation.
Failure timeline
- Move folder B under A while leaving B's old parent still listing B.
- Size(A) now double-counts B's subtree; path walks may loop if a back-link was also left behind.
- Repair: update both ends of every reparent atomically, then recompute cached aggregates on the affected ancestors.
Where trees appear
Syntax: compilers use abstract syntax trees whose children are operands or statements.
Interfaces: DOM and accessibility trees model nested UI structure.
Storage: directory hierarchies and database indexes organize paths and ranges.
Networks: spanning trees connect vertices without routing loops.
Search: game, decision, and state-space trees represent possible futures.
Compression: tries and prefix-code trees exploit shared prefixes.
Exercises
- Prove that any connected undirected graph with n vertices and n − 1 edges is a tree. Where does the proof fail if you drop connectedness?
- For n = 10⁵ in a single-child chain, compare recursive height (call-stack frames) with an iterative parent-array walk. Which fails first in a typical language runtime?
- You need upward “path to root” and downward “list children.” Which representation (or pair) would you store, and what invariant must stay true after a reparent?
Primary sources
- Cormen et al., Introduction to Algorithms (CLRS): elementary graph algorithms; trees as connected acyclic graphs.
- Knuth, The Art of Computer Programming, Vol. 1: fundamental tree representations (child lists, left-child/right-sibling).
- Aho, Hopcroft, Ullman: recursive tree definitions and traversal as structural induction.
Takeaway
A tree is hierarchy with a proof: unique paths, n − 1 edges, disjoint child subtrees. Choose a representation that matches the walks you need, and never let parent and child links disagree.