What Is a Tree? Definition & Terminology

Every node in a rooted tree falls into one of exactly two categories: it either has children or it doesn't. This seemingly simple distinction is one of the most important classifications in tree algorithms.

Nodes with children are called internal nodes (also called branch nodes or inner nodes). Nodes without children are called leaf nodes (also called terminal nodes or external nodes). Understanding this distinction is essential because:

• Base cases in recursive algorithms almost always involve leaf nodes
• Recursive cases always involve internal nodes
• Many tree properties are defined in terms of leaves vs. internal nodes
• Optimization strategies differ based on this classification

A leaf node is a node with zero children. Leaves are the "endpoints" of a tree—there's nowhere farther down to go.

Formal definition:

A leaf (or terminal node or external node) is a vertex in a rooted tree that has no children. Equivalently, in the context of rooted trees, a leaf has degree 0.

In graph-theoretic terms:

In an unrooted tree, a leaf is any vertex with degree 1 (connected to only one other vertex). When the tree is rooted, the definition shifts to "no children" because the root, despite having only downward edges, is not considered a leaf.

In the diagram, the leaf nodes are highlighted in green: C, E, F, and G. Notice that:

• Each leaf has exactly one edge: the edge connecting it to its parent
• No paths "continue downward" from a leaf
• Leaves are at various depths—being a leaf is about children, not depth
• A tree can have a single leaf (a path from root to one endpoint) or many leaves

An internal node is a node with at least one child. Internal nodes are where the tree "branches"—they connect the root to the leaves.

Formal definition:

An internal node (or branch node or inner node) is a vertex in a rooted tree that has one or more children. Equivalently, an internal node has degree ≥ 1.

In the diagram, the internal nodes are highlighted in red: Root, A, B, and D. Notice that:

• The root is internal (unless it's also a leaf—more on this edge case below)
• Each internal node connects the tree structure downward
• B is internal even with just one child (E)—"internal" requires ≥ 1 child, not > 1
• D is internal with two children (F and G)

Important edge case: Single-node trees

If a tree consists of only the root (no other nodes), is the root a leaf or internal? By our definitions:

• It has 0 children → it's a leaf
• It's the only node → there are no other internal nodes

So a single-node tree has exactly one leaf (the root) and zero internal nodes.

Every node in a rooted tree is either a leaf or an internal node—never both, never neither. This creates a partition of the node set:

V = L ∪ I where:

• V is the set of all vertices
• L is the set of leaf nodes
• I is the set of internal nodes
• L ∩ I = ∅ (no overlap)

This partition is fundamental because it determines how we process nodes algorithmically.

There are precise mathematical relationships between tree properties and the count of leaves vs. internal nodes. These relationships help verify algorithms and understand tree structure.

Key relationships:

Proof sketch for binary tree formula (L = I + 1):

1. Total nodes: n = L + I
2. Total edges: n - 1 = L + I - 1
3. Each internal node contributes exactly 2 edges (in a full binary tree)
4. Each edge connects a child to its parent
5. Every non-root node has exactly one incoming edge
6. So total edges = n - 1 (all children) = 2I (edges from internal nodes)
7. Therefore: L + I - 1 = 2I → L = I + 1

This elegant relationship shows why binary trees are mathematically well-behaved.

In recursive tree algorithms, leaf nodes are almost always the base case. This isn't a coincidence—it's structural. Leaves have no children to recurse on, so recursion must stop there.

Standard recursive pattern:

function treeAlgorithm(node) {
    // Base case: leaf node
    if (node.children.length === 0) {
        return computeLeafResult(node);
    }
    
    // Recursive case: internal node
    let result = initialValue;
    for (const child of node.children) {
        const childResult = treeAlgorithm(child);
        result = combine(result, childResult);
    }
    return finalizeResult(node, result);
}

This pattern appears in countless algorithms:

Example: Computing Tree Height

function height(node) {
    // Base case: leaf has height 0 (or 1, depending on definition)
    if (!node || node.children.length === 0) {
        return 0;
    }
    
    // Recursive case: height is 1 + max height of children
    let maxChildHeight = 0;
    for (const child of node.children) {
        maxChildHeight = Math.max(maxChildHeight, height(child));
    }
    return 1 + maxChildHeight;
}

Notice how the leaf check determines when we stop recursing. Without leaves, recursion would never terminate.

While leaves provide base cases, internal nodes aggregate results. They collect information from their children and combine it into a single result for their parent.

This aggregation pattern is the essence of divide and conquer on trees:

1. Divide: The tree structure naturally divides at internal nodes
2. Conquer: Solve subproblems on child subtrees
3. Combine: Internal node aggregates child results

Example: Computing subtree sizes

In this tree:

• Leaves (D, E, F, G) have size 1 — the base case
• B aggregates: size(B) = 1 + size(D) + size(E) = 1 + 1 + 1 = 3
• C aggregates: size(C) = 1 + size(F) + size(G) = 1 + 1 + 1 = 3
• A aggregates: size(A) = 1 + size(B) + size(C) = 1 + 3 + 3 = 7

The aggregation flows bottom-up: leaves produce values, internal nodes combine them.

Code for subtree size computation:

function subtreeSize(node) {
    // Base case: leaf contributes 1
    if (node.children.length === 0) {
        return 1;
    }
    
    // Recursive case: sum all child subtrees + 1 for this node
    let size = 1;  // Count this node
    for (const child of node.children) {
        size += subtreeSize(child);
    }
    return size;
}

Each internal node:

1. Recursively computes sizes of all child subtrees
2. Sums those sizes
3. Adds 1 for itself
4. Returns the total to its parent

While the leaf/internal distinction seems clear, several edge cases require careful consideration:

Robust code handles edge cases:

function processTree(node) {
    // Edge case: empty tree
    if (!node) {
        return { leaves: 0, internal: 0 };
    }
    
    // Edge case: count children safely
    const children = node.children || [];
    
    // Base case: leaf if no children
    if (children.length === 0) {
        return { leaves: 1, internal: 0 };
    }
    
    // Recursive case: aggregate from children
    let leaves = 0;
    let internal = 1;  // This node is internal
    for (const child of children) {
        const childCounts = processTree(child);
        leaves += childCounts.leaves;
        internal += childCounts.internal;
    }
    
    return { leaves, internal };
}

The leaf/internal distinction maps directly to real-world systems:

File Systems:

• Internal nodes = directories (folders)
• Leaf nodes = files
• A directory containing only files has children that are all leaves
• An empty directory is still internal—it can have children

HTML/DOM:

• Internal nodes = elements with children (<div>, <section>, <ul>)
• Leaf nodes = text nodes, empty elements, or elements with no child elements
• Traversal algorithms treat these differently when rendering

Expression Trees:

• Internal nodes = operators (+, -, *, /)
• Leaf nodes = operands (numbers, variables)
• Evaluation: leaves return their value, operators combine child values

Decision Trees (ML):

• Internal nodes = decision points (split on a feature)
• Leaf nodes = predictions (class labels or regression values)
• Classification: traverse until reaching a leaf, which is the prediction

Counting leaves is a fundamental operation. Let's explore multiple approaches:

Recursive Approach:

function countLeaves(node) {
    if (!node) return 0;
    if (node.children.length === 0) return 1;  // This is a leaf
    
    let count = 0;
    for (const child of node.children) {
        count += countLeaves(child);
    }
    return count;
}

Time complexity: O(n) — we visit every node exactly once Space complexity: O(h) — recursion depth equals tree height

Iterative BFS Approach:

function countLeavesIterative(root) {
    if (!root) return 0;
    
    let count = 0;
    const queue = [root];
    
    while (queue.length > 0) {
        const node = queue.shift();
        
        if (node.children.length === 0) {
            count++;  // This is a leaf
        } else {
            for (const child of node.children) {
                queue.push(child);
            }
        }
    }
    
    return count;
}

Time complexity: O(n) Space complexity: O(w) where w is the maximum width of the tree

Iterative DFS Approach (using explicit stack):

function countLeavesDFS(root) {
    if (!root) return 0;
    
    let count = 0;
    const stack = [root];
    
    while (stack.length > 0) {
        const node = stack.pop();
        
        if (node.children.length === 0) {
            count++;
        } else {
            // Push children in reverse for left-to-right processing
            for (let i = node.children.length - 1; i >= 0; i--) {
                stack.push(node.children[i]);
            }
        }
    }
    
    return count;
}

Each approach has trade-offs:

• Recursive is cleanest but uses the call stack
• BFS visits level by level, good for finding the "shallowest" leaves
• DFS with explicit stack gives direct control over memory

Let's consolidate our understanding of the leaf/internal node distinction:

What's next:

With leaves and internal nodes understood, we can now explore subtrees — the recursive structure that makes trees so elegant. Every internal node is the root of its own subtree, and this self-similarity enables powerful recursive solutions.