---
title: 'Tree Terminology'
source: 'https://academia.sh/en/courses/data-structures/tree-terminology'
course: 'Data Structures'
language: en
updated: '2026-08-17T18:08:04+00:00'
license: 'CC BY-SA 4.0'
---

# Tree Terminology

The concepts of root, child, leaf, depth, and height; the definition of a tree, representation options, and areas of use.

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.

```python
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.