What Is a Tree? Definition & Terminology

In the previous page, we established that a tree is a connected acyclic graph—a precise mathematical definition. But when engineers discuss tree algorithms, they don't speak in terms of "connected acyclic graphs." They speak of roots, parents, children, siblings, ancestors, and descendants.

This vocabulary isn't just convenient terminology—it's a mental model that transforms how we think about trees. Rather than viewing a tree as an abstract collection of vertices and edges, this vocabulary imposes a hierarchical perspective that aligns with how tree algorithms actually work.

This vocabulary comes from an analogy to family trees—and like all good analogies, it illuminates while occasionally misleading. We'll embrace the intuition while being rigorous about the definitions.

The formal tree definition (connected acyclic graph) describes what we call a free tree or unrooted tree. In an unrooted tree, no vertex is special—all vertices are structurally equivalent. There's no "up" or "down," no "parent" or "child."

But algorithms need direction. We need to know where to start, which way to traverse, and how to organize our thinking. This is where rooted trees enter.

Definition of a Rooted Tree:

A rooted tree is a tree with one designated vertex called the root. The root establishes direction: all edges are considered to point away from the root (toward the "leaves").

The diagram shows the same underlying tree rooted at two different vertices. Notice how the same five vertices and four edges produce different hierarchies depending on which vertex we designate as the root.

Key insight: Choosing a root doesn't change the tree's structure—it changes our perspective on the structure. The connected acyclic graph remains the same; only our interpretation changes.

The root is the designated starting vertex of a rooted tree. It establishes the entire hierarchical structure—every other concept (parent, child, etc.) is defined relative to the root.

Formal definition of Root:

The root is a distinguished vertex in a rooted tree from which all other vertices can be reached by following edges in a single direction (downward in conventional drawings).

In the diagram, the root (highlighted in green) sits at the top. All other nodes are below it in the hierarchy. Notice that:

• The root has three children (A, B, C)
• Every other node can trace a unique path back to the root
• If we removed the root and its edges, we'd have three disconnected subtrees

Convention: Trees are almost always drawn with the root at the top and leaves at the bottom—opposite to how biological trees grow. This convention matches how we read (top to bottom) and became standard in computer science.

The parent-child relationship is the atomic unit of tree structure. Every edge in a rooted tree represents exactly one parent-child relationship.

Formal definitions:

For any edge (u, v) in a rooted tree where u is closer to the root:

• u is the parent of v
• v is the child of u

Alternatively:

If we can reach v by going downward (away from the root) from u in exactly one step, then u is v's parent and v is u's child.

Accessing parent and children in code:

Tree representations store these relationships explicitly:

class TreeNode {
    constructor(value) {
        this.value = value;
        this.parent = null;     // Pointer to parent (may be null for root)
        this.children = [];      // Array of child nodes
    }
}

For binary trees specifically:

class BinaryTreeNode {
    constructor(value) {
        this.value = value;
        this.parent = null;      // Optional: not always stored
        this.left = null;        // Left child
        this.right = null;       // Right child
    }
}

Just like in a family, siblings are nodes that share the same parent.

Formal definition:

Two distinct vertices are siblings if and only if they have the same parent.

This is a symmetric relationship: if A is a sibling of B, then B is a sibling of A.

In the diagram:

• A, B, C are siblings (parent: Root) — shown in orange
• D, E, F are siblings (parent: A) — shown in purple
• D and A are NOT siblings (different parents)
• B and E are NOT siblings (different parents)

Important properties of siblings:

1. Same depth: All siblings are at the same depth in the tree
2. Same distance to common ancestor: Siblings share their parent as their lowest common ancestor
3. Root has no siblings: The root is the only vertex without a parent, hence no siblings
4. Leaf siblings: It's possible for all children of a node to be leaves

An ancestor is any node on the path from a given node up to the root. This extends the parent relationship across multiple generations.

Formal definition:

Vertex u is an ancestor of vertex v if u lies on the unique path from v to the root (inclusive of v and the root).

Alternative recursive definition:

A vertex v is an ancestor of itself.<br> If u is an ancestor of v, and w is the parent of u, then w is also an ancestor of v.

Note: Under this definition, every node is an ancestor of itself. Some texts use "proper ancestor" to exclude the node itself:

Vertex u is a proper ancestor of vertex v if u is an ancestor of v and u ≠ v.

In the diagram, the node G (red) has the following ancestors (green path):

• E (parent of G)
• C (grandparent of G)
• A (great-grandparent of G)
• Root (the ultimate ancestor)
• G itself (if using the inclusive definition)

The ancestors form a straight line from any node to the root—this is the unique path guaranteed by the tree structure.

Finding ancestors algorithmically:

function getAncestors(node) {
    const ancestors = [];
    let current = node;
    
    while (current !== null) {
        ancestors.push(current);
        current = current.parent;  // Move up toward root
    }
    
    return ancestors;  // [node, parent, grandparent, ..., root]
}

This runs in O(h) time where h is the height of the tree (maximum depth of any node).

A descendant is the inverse of an ancestor. While ancestors look upward toward the root, descendants look downward toward the leaves.

Formal definition:

Vertex v is a descendant of vertex u if u is an ancestor of v.

Equivalently:

Vertex v is a descendant of u if the unique path from v to the root passes through u.

In the diagram, the node A (red) has the following descendants (blue):

• C and D (children of A)
• E and F (grandchildren via C)
• G (grandchild via D)
• A itself (if using inclusive definition)

Notice that the descendants of A form a complete subtree—a tree in their own right with A as the root.

Finding descendants algorithmically:

function getDescendants(node) {
    const descendants = [];
    
    function collectDescendants(current) {
        descendants.push(current);
        for (const child of current.children) {
            collectDescendants(child);  // Recursive DFS
        }
    }
    
    collectDescendants(node);
    return descendants;  // [node, all nodes in subtree]
}

This runs in O(k) time where k is the number of nodes in the subtree—we must visit every descendant.

Understanding how these relationships connect is crucial for algorithmic thinking:

Inverse relationships:

• u is a parent of v ⟺ v is a child of u
• u is an ancestor of v ⟺ v is a descendant of u

Every relationship has an inverse. When you say "A is B's parent," you're simultaneously saying "B is A's child." These are two views of the same edge.

Before leaving core vocabulary, we must define the degree of a node—a concept often confused with children count.

In graph theory:

The degree of a vertex is the number of edges incident to it.

In rooted trees, we distinguish:

The degree (or branching factor) of a node in a rooted tree is typically defined as the number of its children.

In the diagram, each node is labeled with its degree (number of children):

• Root: degree 3 (children: A, B, C)
• A: degree 2 (children: D, E)
• B: degree 0 (no children — a leaf)
• C: degree 3 (children: F, G, H)
• H: degree 1 (child: I)
• D, E, F, G, I: degree 0 (all leaves)

The degree of the tree is often defined as the maximum degree of any node. This tree has degree 3.

Let's solidify these concepts with a concrete example. Consider this file system tree:

C:\
├── Users\
│   ├── Alice\
│   │   ├── Documents\
│   │   └── Downloads\
│   └── Bob\
│       └── Desktop\
├── Program Files\
│   ├── Chrome\
│   └── VSCode\
└── Windows\
    └── System32\

You now have complete fluency in the language of trees. Let's consolidate:

What's next:

With the hierarchical vocabulary established, we can now distinguish between two critical types of nodes: leaf nodes (with no children) and internal nodes (with at least one child). These categories are fundamental to tree algorithms and traversal strategies.