Trees: The Vocabulary of Hierarchy

A node that may point to several other nodes, with no cycles back, is a tree.

That is the linked list generalized from a chain to branches. Instead of one next pointer per node there are many, usually held in a list of children.

Read the relationship the other way and it is just as useful: a linked list is a tree in which every node has at most one child, so everything learned about traversal in unit 4 still applies, only now each step has a choice of directions.

The no-cycles condition is what keeps it a tree rather than a graph. Nothing below a node can point back up to it, which is why a tree traversal terminates without needing the seen set that BFS required in lesson 5-3.

Data with a hierarchy

Plenty of data is naturally nested: folders inside folders, HTML elements inside elements, company org charts, replies under comments. The structure for nesting is the tree.

The vocabulary is used constantly from here on, so it is worth learning now.

• root is the single top node.
• child and parent describe a node directly below or above another.
• leaf is a node with no children.
• subtree is any node plus everything below it, itself a complete tree.
• depth of a node is how many steps it sits below the root.
• height of a tree is the longest root-to-leaf path.

The subtree entry in that list is doing more work than the others. It says that every child of a node is the root of a smaller tree of exactly the same shape, which is what makes recursion fit trees so naturally.

A function that handles one node can simply call itself on each child, and it does not need to know how deep the tree goes or how many children each node has.

Height matters for a different reason. It is the number of steps a search from the root can take, so unit 7's later lessons spend their effort on keeping it small.

Counting nodes and measuring height

A tree node is a value plus a list of children, where a linked list node held a single next pointer.

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

root = TreeNode("/")
home = TreeNode("home")
etc = TreeNode("etc")
docs = TreeNode("docs")
pics = TreeNode("pics")
root.children = [home, etc]
home.children = [docs, pics]

def count_nodes(node):
    total = 1
    for child in node.children:
        total += count_nodes(child)
    return total

def height(node):
    if not node.children:
        return 0
    return 1 + max(height(c) for c in node.children)

print("nodes:", count_nodes(root))
print("height:", height(root))

Output

nodes: 5
height: 2

Both functions use the subtree idea in the same way, handling the current node and recursing on each child, and neither has any idea how large the tree is.

In count_nodes the current node contributes total = 1 and each child contributes the size of its own subtree. The recursion stops on its own at a leaf, because a node with no children never enters the loop.

height needs an explicit base case instead. A leaf returns 0 since no steps remain below it, and any other node returns 1 plus the tallest of its children's heights, where max picks the longest branch.

The height of 2 traces the path from / to home to docs, which is two steps. The etc branch is only one step deep, and max discards it.

Counting leaves

The same tree, with a function that counts only the childless nodes.

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

root = TreeNode("/")
home = TreeNode("home")
etc = TreeNode("etc")
docs = TreeNode("docs")
pics = TreeNode("pics")
root.children = [home, etc]
home.children = [docs, pics]

def count_leaves(node):
    if not node.children:
        return 1
    return sum(count_leaves(c) for c in node.children)

print("leaves:", count_leaves(root))
print("leaves under home:", count_leaves(home))

Output

leaves: 3
leaves under home: 2

The base case comes first. A childless node is a leaf, so it returns 1 and the recursion stops there.

The recursive case sums the children's leaf counts and adds nothing of its own, because a node with children is by definition not a leaf. That single difference is all that separates this from count_nodes, which added 1 at every node.

The leaves here are docs, pics, and etc, which is why the whole tree reports 3.

The second call is the interesting one. Passing home instead of root counts leaves in home's subtree alone and returns 2, with no change to the function. That works because a subtree is a complete tree, so the same code answers the same question at any depth.

False. Pics is not the root of a subtree containing home.

Subtrees grow downward. pics is a leaf, so its subtree is just itself, and home sits above it as its parent, which puts it permanently outside.

The confusion is worth naming, because parent and child are easy to flip. Containment in a tree always points from ancestor to descendant, so the statement is true only with the two names swapped: home's subtree contains pics.

True statements about this tree run the other direction. docs, pics, and etc have no children, home directly contains docs and pics, and the root's subtree contains everything.