Trees

A tree is a set of nodes connected by parent–child links, starting from a single root. Every node except the root has exactly one parent; a node can have any number of children. Nodes without children are leaves. The depth of a node is its distance from the root; the height of the tree is the greatest depth.

The one-parent rule is what makes something a tree: there's exactly one path from the root to each node, and no loops. Any data with a strict containment or reporting hierarchy fits naturally.

tree = {"/": {"home": {"ann": {"a.txt": None}, "bo": {}}, "etc": {"hosts": None}}}

class Node:
    def __init__(self, name, children=None):
        self.name, self.children = name, children or []

struct Node {
    name: String,
    children: Vec<Node>,   // each child owned by exactly one parent
}
let root = Node { name: "/".into(), children: vec![
    Node { name: "home".into(), children: vec![] },
]};

Trees appear wherever something contains something else, and the one-parent rule holds. A few patterns worth recognising:

Hierarchies: file systems, org charts, product categories. Documents: HTML (the DOM), JSON, XML, an abstract syntax tree when a compiler parses code. Decisions: a decision tree in a support script or a machine-learning model, where each answer leads to exactly one next question.

The moment something needs two parents, it stops being a tree. A file that lives in two folders (a hard link), an employee with two managers, a workflow step that waits for two others: those are graphs, covered later in this course.

A binary tree is a tree where each node has at most two children, called left and right. On its own it's just a shape; it becomes useful with a rule about what goes where. The two most important rules come later in this course: the binary search tree (left smaller, right larger) and the heap (parent smaller than both children).

One number matters for every binary tree: its height. A tree with n nodes can be as short as about log₂ n levels, when it's balanced, or as tall as n levels, when every node has one child. Since most operations walk from the root down, height decides whether they cost O(log n) or O(n).

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def height(n):
    return 0 if n is None else 1 + max(height(n.left), height(n.right))

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}
fn height(n: &Option<Box<TreeNode>>) -> usize {
    match n { None => 0, Some(b) => 1 + height(&b.left).max(height(&b.right)) }
}