What Is a Tree? Definition & Terminology

Here's the most beautiful property of trees: every subtree is itself a tree.

This might sound obvious, but the implications are profound. When you look at a tree and focus on any internal node, you're looking at a smaller tree. That smaller tree has the same properties, the same structure, and can be processed with the same algorithms as the original. This self-similarity is why recursion and trees are a perfect match—and why tree algorithms are often stunningly elegant.

The recursive nature of trees isn't just an algorithmic convenience—it's the fundamental reason trees are so powerful. Once you internalize "every internal node is the root of its own subtree," you'll start seeing trees differently. Problems that seemed daunting become tractable because you can reduce them to smaller instances of themselves.

A subtree is a portion of a tree that is itself a complete tree. Every node in a rooted tree is the root of exactly one subtree.

Formal definition:

Given a rooted tree T with root r, and any vertex v in T, the subtree rooted at v consists of:

1. The vertex v itself
2. All descendants of v
3. All edges connecting v to its descendants

Alternative definition:

The subtree rooted at v is the induced subgraph of T containing v and all vertices reachable by moving downward (away from the root) from v.

In the diagram, the subtree rooted at A is highlighted:

• Root of subtree: A (dark green)
• Members of subtree: C, D, G, H (light green)
• The rest of the tree (Root, B, E, F) is NOT part of this subtree

Notice that this subtree is a valid tree on its own:

• A is connected (to C and D)
• It's acyclic
• A has 4 descendants and itself = 5 nodes total

Subtrees inherit all the fundamental properties of trees, plus they have organizational properties within the larger tree:

Trees are recursively defined. This means the very definition of a tree refers to smaller trees:

Recursive definition of a rooted tree:

A rooted tree is either:

1. Base case: A single node (which is both the root and a leaf)
2. Recursive case: A root node connected to one or more child subtrees, where each child subtree is itself a rooted tree

This definition is circular in the mathematical sense—but it's well-founded because each recursive step involves strictly smaller structures, bottoming out at single nodes.

This recursive structure is why trees and recursion are natural partners:

// The structure of almost every recursive tree function:
function solveForTree(node) {
    // Base case: leaf or empty
    if (!node || isLeaf(node)) {
        return baseResult;
    }
    
    // Recursive case: solve for each child subtree
    let results = [];
    for (const child of node.children) {
        results.push(solveForTree(child));  // Recursive call
    }
    
    // Combine results from subtrees
    return combineResults(node, results);
}

The function's structure mirrors the tree's structure: we solve the problem for a tree by solving it for each subtree and combining.

The most powerful skill in tree algorithm design is thinking in subtrees. Instead of thinking about the entire tree, you:

1. Consider what information you need from each child subtree
2. Assume you magically have that information (trust the recursion)
3. Figure out how to combine that information at the current node
4. Define the base case for leaves

This is the "recursive leap of faith" applied to trees.

Example: Computing the maximum depth of a tree

Step 1: What do we need from child subtrees? The maximum depth of each child subtree.

Step 2: Assume we have it (trust recursion) Each child gives us a number: the maximum depth in that subtree.

Step 3: How do we combine at the current node? The maximum depth from the current node is 1 + the maximum of child depths.

Step 4: Base case for leaves? A leaf has depth 0 (no children to go deeper).

function maxDepth(node) {
    // Base case
    if (!node) return 0;
    if (node.children.length === 0) return 0;
    
    // Get information from each child subtree
    let maxChildDepth = 0;
    for (const child of node.children) {
        maxChildDepth = Math.max(maxChildDepth, maxDepth(child));
    }
    
    // Combine: add 1 for the current level
    return 1 + maxChildDepth;
}

Let's apply the four-step subtree thinking process to several classic problems:

Problem 1: Count all nodes in a tree

function countNodes(node) {
    if (!node) return 0;
    
    let count = 1;  // Count this node
    for (const child of node.children) {
        count += countNodes(child);  // Add child subtree counts
    }
    return count;
}

Problem 2: Find the sum of all node values

function sumValues(node) {
    if (!node) return 0;
    
    let sum = node.value;
    for (const child of node.children) {
        sum += sumValues(child);
    }
    return sum;
}

Problem 3: Check if a value exists in the tree

function containsValue(node, target) {
    if (!node) return false;
    
    // Check this node
    if (node.value === target) return true;
    
    // Check child subtrees
    for (const child of node.children) {
        if (containsValue(child, target)) return true;
    }
    return false;
}

Recursive tree algorithms fall into two broad patterns based on how information flows:

Bottom-Up (Postorder-style):

• Information flows from leaves toward the root
• First recurse on children, then process the current node
• Child results are available when processing the parent
• Examples: counting nodes, computing height, summing values

Top-Down (Preorder-style):

• Information flows from the root toward leaves
• Process the current node first, then recurse
• Parent context is passed down to children
• Examples: computing depth, printing paths, certain validations

Bottom-Up Example: Height

function height(node) {
    if (!node || node.children.length === 0) return 0;
    
    // First: get heights from all children (recurse)
    let maxChildHeight = 0;
    for (const child of node.children) {
        maxChildHeight = Math.max(maxChildHeight, height(child));
    }
    
    // Then: compute this node's height
    return 1 + maxChildHeight;
}

Top-Down Example: Compute Depth of Each Node

function computeDepths(node, currentDepth = 0) {
    if (!node) return;
    
    // First: process this node
    node.depth = currentDepth;
    
    // Then: recurse with updated depth
    for (const child of node.children) {
        computeDepths(child, currentDepth + 1);
    }
}

In binary trees, each node has at most two children, conventionally called the left child and right child. This creates exactly two special subtrees:

Definitions:

The left subtree of a node is the subtree rooted at its left child (or empty if no left child).

The right subtree of a node is the subtree rooted at its right child (or empty if no right child).

In the diagram:

• Left subtree of Root: highlighted in blue (L, LL, LR)
• Right subtree of Root: highlighted in pink (Right, RL, RR)

The left/right distinction has profound implications:

• Many algorithms depend on it (BST operations, traversals)
• It creates a natural ordering of children
• Operations often "go left" or "go right" based on comparisons

Binary tree recursive pattern:

function binaryTreeAlgorithm(node) {
    // Base case: null node
    if (!node) {
        return baseResult;
    }
    
    // Recurse on left and right subtrees
    const leftResult = binaryTreeAlgorithm(node.left);
    const rightResult = binaryTreeAlgorithm(node.right);
    
    // Combine results
    return combine(node.value, leftResult, rightResult);
}

This pattern is ubiquitous in binary tree algorithms:

// Height of binary tree
function height(node) {
    if (!node) return -1;  // or 0, depending on definition
    return 1 + Math.max(height(node.left), height(node.right));
}

// Size of binary tree
function size(node) {
    if (!node) return 0;
    return 1 + size(node.left) + size(node.right);
}

Many tree problems are explicitly about subtrees. Here are common patterns:

Pattern 1: Find subtrees satisfying a condition

// Count subtrees with sum equal to target
function countSubtreesWithSum(node, target) {
    if (!node) return { count: 0, sum: 0 };
    
    const left = countSubtreesWithSum(node.left, target);
    const right = countSubtreesWithSum(node.right, target);
    
    const sum = node.value + left.sum + right.sum;
    let count = left.count + right.count;
    if (sum === target) count++;
    
    return { count, sum };
}

Pattern 2: Check if one tree is a subtree of another

function isSubtree(s, t) {
    if (!s) return !t;
    if (isSameTree(s, t)) return true;
    return isSubtree(s.left, t) || isSubtree(s.right, t);
}

function isSameTree(s, t) {
    if (!s && !t) return true;
    if (!s || !t) return false;
    return s.value === t.value && 
           isSameTree(s.left, t.left) && 
           isSameTree(s.right, t.right);
}

Recursive tree algorithms are elegant but require careful analysis:

Time Complexity:

Most tree algorithms visit each node exactly once, giving O(n) time complexity. However, some naive recursive solutions are much worse:

// INEFFICIENT: O(n²) for unbalanced trees
function isBalanced_Naive(node) {
    if (!node) return true;
    
    // height() is O(n), and we call it at each node!
    const leftHeight = height(node.left);
    const rightHeight = height(node.right);
    
    if (Math.abs(leftHeight - rightHeight) > 1) return false;
    
    return isBalanced_Naive(node.left) && isBalanced_Naive(node.right);
}

// EFFICIENT: O(n) by computing height bottom-up
function isBalanced_Efficient(node) {
    function checkHeight(node) {
        if (!node) return 0;
        
        const left = checkHeight(node.left);
        if (left === -1) return -1;  // Left subtree unbalanced
        
        const right = checkHeight(node.right);
        if (right === -1) return -1;  // Right subtree unbalanced
        
        if (Math.abs(left - right) > 1) return -1;  // This node unbalanced
        
        return 1 + Math.max(left, right);
    }
    return checkHeight(node) !== -1;
}

Space Complexity:

Recursive algorithms use call stack space proportional to the recursion depth:

• Balanced tree: O(log n) stack depth — efficient
• Unbalanced tree: O(n) stack depth — can cause stack overflow

Mitigation strategies:

1. Tail recursion (when applicable and supported by the language)
2. Explicit stack (convert to iterative with manual stack)
3. Morris traversal (O(1) space for certain traversals)
4. Iterative deepening (for certain problems)

Let's consolidate the power of subtree thinking:

Module Complete:

You now have a complete understanding of tree fundamentals:

• Page 1: Trees are connected acyclic graphs
• Page 2: Vocabulary — root, parent, child, sibling, ancestor, descendant
• Page 3: The leaf/internal node partition and its algorithmic significance
• Page 4: Subtrees and the recursive nature of trees

With this foundation, you're ready to explore tree properties (depth, height, levels), specific tree types (binary trees, N-ary trees), and traversal algorithms that visit every node systematically.