Tree Terminology

The structures covered so far have been linear: every element had at most one predecessor and one successor. This broke in the Disjoint Sets lesson — groups were held in structures where every node has one parent, but a parent can have more than one child.

This topic takes up that structure in its own right. A tree is the fundamental structure for modeling branching relationships, and it appears at every layer of computer science.

Definition

A tree is a node–edge structure that satisfies two conditions:

1. All nodes are connected to one another; none is disconnected.
2. There is no cycle; there is exactly one path between any two nodes.

The numerical consequence of these two conditions is this: a tree with $n$ nodes has exactly $n - 1$ edges. Adding one more edge creates a cycle; removing one edge splits the structure in two.

Most trees are rooted: one node is chosen as the root, and every edge is treated as pointing away from it. Throughout this course, “tree” means a rooted tree unless stated otherwise.

Terminology

                 (12)          ← root, depth 0
                /    \
            (18)      (7)      ← depth 1
           /   \        \
       (25)   (14)      (30)   ← depth 2, all leaves

Term	Meaning	In the example
Root	The single node with no parent	12
Parent	The node directly above a node	18’s parent is 12
Child	A node directly below a node	12’s children are 18 and 7
Sibling	Children of the same parent	25 and 14
Leaf	A node with no children	25, 14, 30
Internal node	A node with at least one child	12, 18, 7
Ancestor	Nodes on the path from the root to a node	25’s ancestors: 18, 12
Descendant	All nodes below a node	18’s descendants: 25, 14
Subtree	A node and all its descendants	the subtree rooted at 18
Depth	The number of edges from the root to a node	25’s depth is 2
Height	The number of edges from a node to its farthest leaf	12’s height is 2
Branching factor	A node’s number of children	2 for 12

Depth and height are frequently confused. Depth is measured from above, height from below. The root’s depth is zero and leaves have the largest depth; leaves have height zero and the root has the largest height. A tree’s height is the height of its root.

A structure formed by multiple disconnected trees is called a forest. The representation in the Disjoint Sets lesson was a forest: each group was a separate tree.

Where Trees Appear

A tree is the structure of any relationship defined as “everything has one thing above it, but a thing above can have more than one thing below it”:

• File system. Directories and files; from the root directory to the leaves. The directory hierarchy in the Linux curriculum has this structure.
• Document structure. Nested tags in markup languages; every tag has one container and can have multiple contents.
• Parse tree. The abstract syntax tree established in the How Computers Work course; expression precedence was encoded in the shape of the tree.
• Decision structures. A question at every node, an answer on every branch; decision trees in machine learning follow this arrangement.
• Organization charts and category hierarchies. Direct modeling.

Such a wide range of use means that the operations defined on trees — traversal, search, depth computation — turn up again and again everywhere.

Representation Options

A tree is stored in three main forms.

Child lists. Every node holds a list of its children. This is the most natural representation for general trees; the branching factor can vary. Its cost is a list structure per node.

First child – next sibling. Every node holds two links: its first child and its next sibling. A variable number of children is represented with a fixed number of links; the general tree is reduced to a binary structure.

Array representation. Nodes are held in an array, and the relationship is computed with index arithmetic. This applies only if the tree’s shape is regular; it will be defined for binary trees in the next lesson.

class TreeNode:
    """General tree node: a value and a list of children."""

    def __init__(self, value: int) -> None:
        self.value = value
        self.children: list["TreeNode"] = []

    def add_child(self, child: "TreeNode") -> "TreeNode":
        self.children.append(child)
        return child


def height(node: TreeNode) -> int:
    """Number of edges from the node to its farthest leaf."""
    if not node.children:
        return 0                                  # a leaf's height is zero
    return 1 + max(height(c) for c in node.children)


def node_count(node: TreeNode) -> int:
    return 1 + sum(node_count(c) for c in node.children)


def leaf_count(node: TreeNode) -> int:
    if not node.children:
        return 1
    return sum(leaf_count(c) for c in node.children)


root = TreeNode(12)
left = root.add_child(TreeNode(18))
right = root.add_child(TreeNode(7))
left.add_child(TreeNode(25))
left.add_child(TreeNode(14))
right.add_child(TreeNode(30))

print(height(root), node_count(root), leaf_count(root))   # 2 6 3
print(height(left), height(right))                          # 1 1

It is not a coincidence that all three functions are written recursively: a tree’s definition is itself recursive — a tree is a root and its subtrees. The Programming Fundamentals course stated that “recursion is natural when a problem’s definition branches”; trees are the canonical example of that statement.

Verifying the Structure

Whether a structure is really a tree is tested with two conditions: the edge count must be one less than the node count, and the structure must be connected. Together, the two also guarantee acyclicity.

In practice a third test is also applied: every node must be reached from only one place above it. If a node has edges from two separate parents, the structure is not a tree but a general graph; traversal algorithms visit that node twice and the result breaks.

Why Height Matters

The cost of almost every operation on a tree is proportional not to the node count but to the height: a path from the root down to a leaf is followed.

This makes one question directly important: what can the height of an $n$-node tree be?

• Best case: If every node distributes its children in a balanced way, the height is $O(\log n)$.
• Worst case: If every node has a single child, the tree turns into a linked list and the height is $O(n)$.

For this reason, the first question to ask when evaluating a tree structure is what bounds its height. The gap between the two extremes is the central concern of the rest of this topic: keeping search trees balanced is exactly the effort of keeping height within a logarithmic bound.

Summary

• A tree is an acyclic, connected node structure; a tree with $n$ nodes has $n-1$ edges.
• In a rooted tree, edges point away from the root; every node except the root has exactly one parent.
• Depth is measured downward from the root, height from a node to a leaf; a tree’s height is the height of its root.
• Trees are the model for every branching relationship, from file systems to parse structures.
• Representation is done with child lists, first child–next sibling, or index arithmetic.
• Operation costs are proportional to height, not node count; height varies between logarithmic and linear depending on balance.

Next Step

In general trees the branching factor varies, and this complicates both representation and analysis. The next lesson takes up the special case where every node has at most two children — binary trees — and the regular representation options this constraint brings.