Chapter 94

Home

Tree Basics and Traversals

A tree is an undirected graph with no cycles. Root it at any node, then each node has a parent and children. Depth-first traversals (preorder, inorder, postorder) visit nodes in different orders for different purposes.

Tree Terminology

Root

The top node. Every other node descends from it. Choose arbitrarily for an unrooted tree.

Subtree

A node and all its descendants. Recursive structure makes trees ideal for DP.

Depth

Distance from root. Root depth = 0. BFS from root computes all depths.

Height

Depth of deepest leaf in the subtree.

C++ — tree traversals

vector> adj;
vector parent, depth;

void dfs(int u, int p) {
    parent[u] = p;
    depth[u] = (p == -1) ? 0 : depth[p] + 1;

    // Preorder: process u before children
    for (int v : adj[u]) if (v != p) dfs(v, u);
    // Postorder: children processed before returning
}

Key Takeaways