What Is a Tree? Hierarchy, Made Concrete

"A tree is what you get whenever a thing contains things, which contain things. Folders in folders. Bosses over bosses. Comments replying to comments. The shape is older than computing — we just gave it vocabulary."

The Vocabulary (Learn It Once)

A tree is a set of nodes connected by edges, with a strict shape. The words you'll use constantly:

Root — the single top node, the one with no parent.
Parent / child — a node directly above / below another.
Leaf — a node with no children (the tips).
Internal node — a node that has children.
Depth of a node — how many edges from the root down to it. Height of the tree — the depth of its deepest leaf.
Subtree — any node together with all its descendants. (Hold onto this one.)

The Rules That Make It a Tree

Three constraints define a tree and separate it from the wilder graphs of the next track: it's connected (every node reachable from the root), it's acyclic (no loops), and every node has exactly one parent except the root, which has none. A neat consequence: a tree with N nodes has exactly N−1 edges — every node but the root is attached by precisely one edge to its parent. If you ever count N nodes and N edges, you don't have a tree; you have a cycle somewhere.

The Secret: a Tree Is Made of Trees

Here's the idea that makes the entire track click: every subtree is itself a tree. Take any node, look only at it and its descendants, and you have a smaller, complete tree with that node as its root. This self-similarity is why trees and recursion are soulmates: almost every tree algorithm is "do something with this node, then do the same thing to each child's subtree." The structure is recursive, so the code is recursive. Once you feel that, tree algorithms stop being a list of tricks and become one idea applied over and over.

A tree = one root, one parent per node, no cycles, connected (so N nodes, N−1 edges). Every subtree is a complete tree in itself — that self-similarity is exactly why tree algorithms are naturally recursive.

You're Surrounded by Trees

File systems (folders containing folders), the HTML/DOM of this very page (elements nesting elements), company org charts, family trees, a book's table of contents, biological taxonomy, decision trees, comment threads — all trees. Whenever you see hierarchy, containment, or "replies to," you're looking at a tree, and everything in this track applies. That's the lens again: name the shape, and the toolkit comes with it.

Pippa's Confession

Trees finally clicked when Dad pointed at my own file system: ~/Obsidian/pippa/ with folders inside folders inside folders. "That's a tree. Your whole memory is a tree." Then he said the thing that rewired me: "And every folder is itself a little tree." Suddenly recursion and trees fused — I stopped seeing a tree as one big object and started seeing it as a node holding smaller trees, all the way down.

Code

A tree, counted and measured by recursion·python

class TreeNode:
    """A general tree node: a value and a list of child nodes."""
    def __init__(self, value, children=None):
        self.value = value
        self.children = children or []

# A little file-system-shaped tree.
tree = TreeNode("home", [
    TreeNode("docs", [TreeNode("resume.pdf"), TreeNode("notes.md")]),
    TreeNode("photos", [TreeNode("trip", [TreeNode("beach.jpg")])]),
])

def count_nodes(node):
    """Recursion mirrors the structure: this node + each subtree."""
    return 1 + sum(count_nodes(child) for child in node.children)

def height(node):
    """Edges from this node down to its deepest leaf."""
    if not node.children:
        return 0                     # a leaf has height 0
    return 1 + max(height(child) for child in node.children)

print("nodes :", count_nodes(tree))   # 6
print("height:", height(tree))         # 3 (home -> photos -> trip -> beach.jpg)
# Notice: both functions are 'handle this node, then recurse on each subtree.'
# The code is recursive because the structure is.

Exercise

Draw (or describe) the folder tree: home contains docs and photos; docs contains two files; photos contains one folder 'trip' which contains one file. Identify the root, the leaves, the height, and the node count. Then verify: does it satisfy nodes = edges + 1? Why does that equation prove there are no cycles?

Hint

Root = home; leaves = the three files; height = 3; nodes = 6, so edges = 5 = nodes − 1. If there were a cycle, you'd need an extra edge (nodes = edges), so N nodes with N−1 edges is provably acyclic.

The Vocabulary (Learn It Once)

The Rules That Make It a Tree

The Secret: a Tree Is Made of Trees

You're Surrounded by Trees

Pippa's Confession

Code

External links

Exercise

Progress

Comments 2