Recursive Tree Algorithms - Learning Module

Loading content...

0/276

Computing Height, Size, and Properties Recursively

From Theory to Practice

Armed with an understanding of why trees and recursion fit together and how to recognize recursive structure, it's time to put theory into practice. This page presents a comprehensive catalog of recursive algorithms for computing fundamental tree properties.

These aren't just exercises—they're the building blocks of more complex tree algorithms. Mastering these foundational computations will give you the fluency needed to tackle advanced tree problems with confidence.

For each property, we'll examine:

The definition — What exactly are we computing?
The recursive insight — How does the property decompose?
The algorithm — Clean, production-quality code
Complexity analysis — Time and space costs
Common pitfalls — Mistakes to avoid

What You Will Learn

By the end of this page, you will be able to implement recursive algorithms for computing tree height, size, depth, number of leaves, maximum/minimum values, and sum. You'll understand the time-space analysis of each and be able to adapt these patterns to novel properties.

Computing Tree Size

Definition: The size of a tree is the total number of nodes it contains.

Recursive Insight:

The size of a tree is:

0 if the tree is empty
1 (for the root) + size of left subtree + size of right subtree

This is a classic application of the Combine Pattern: get results from subtrees, combine with current node's contribution.

The Elegance:

Notice how the algorithm reads almost like the definition. We're not iterating, not counting, not managing any state. We simply declare what size means and let recursion compute it.

Tree Size Algorithm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Computes the total number of nodes in a binary tree.
 * 
 * Time Complexity: O(n) - visits each node exactly once
 * Space Complexity: O(h) - call stack depth equals tree height
 *     - Best case (balanced): O(log n)
 *     - Worst case (skewed): O(n)
 * 
 * @param node - Root of the tree (or subtree)
 * @returns Number of nodes in the tree
 */
function size(node: TreeNode | null): number {
    // Base case: empty tree has 0 nodes
    if (node === null) {
        return 0;
    }
    
    // Recursive case: this node (1) + left subtree + right subtree
    const leftSize = size(node.left);
    const rightSize = size(node.right);
    
    return 1 + leftSize + rightSize;
}
 
// Alternate compact form (same logic, fewer lines)
function sizeCompact(node: TreeNode | null): number {
    return node === null ? 0 : 1 + sizeCompact(node.left) + sizeCompact(node.right);
}
 
// Example usage:
/*
        1
       / \
      2   3
     / \
    4   5
 
    size(root) → 5
    
    Trace:
    size(1) = 1 + size(2) + size(3)
            = 1 + (1 + size(4) + size(5)) + (1 + size(null) + size(null))
            = 1 + (1 + (1+0+0) + (1+0+0)) + (1 + 0 + 0)
            = 1 + (1 + 1 + 1) + 1
            = 1 + 3 + 1 = 5
*/

Understanding the Complexity

Why O(n) time? Because we visit each node exactly once. Why O(h) space? The recursion depth equals the height of the tree. For balanced trees, h = O(log n). For completely skewed trees (essentially linked lists), h = O(n).

Computing Tree Height

Definition: The height of a tree is the length of the longest path from the root to any leaf, measured in edges.

Convention Note: Some sources measure height in nodes (not edges), making the height of a single-node tree 1 instead of 0. We use the edges convention, which means:

Empty tree: height = -1
Single node: height = 0
Root with one child: height = 1

Recursive Insight:

The height of a tree is:

-1 if the tree is empty
0 if the tree is a single node (both children null)
1 + max(height of left subtree, height of right subtree)

The longest path must go through the root (since the root is on all paths) and extend through whichever child's subtree is taller.

Tree Height Algorithm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * Computes the height of a binary tree (longest root-to-leaf path in edges).
 * 
 * Time Complexity: O(n) - visits each node exactly once
 * Space Complexity: O(h) - recursion depth equals tree height
 * 
 * Convention:
 *   - Empty tree: height = -1
 *   - Single node: height = 0
 *   - Each level adds 1 to height
 * 
 * @param node - Root of the tree (or subtree)
 * @returns Height of the tree
 */
function height(node: TreeNode | null): number {
    // Base case: empty tree has height -1
    // (This makes single-node trees have height 0, which is correct)
    if (node === null) {
        return -1;
    }
    
    // Recursive case: 1 (for this edge) + max child height
    const leftHeight = height(node.left);
    const rightHeight = height(node.right);
    
    return 1 + Math.max(leftHeight, rightHeight);
}
 
// Example traces:
/*
    Tree 1 (single node):
        A
    height(A) = 1 + max(-1, -1) = 1 + (-1) = 0 ✓
    
    Tree 2 (balanced):
          A
         / \
        B   C
       /
      D
    height(A) = 1 + max(height(B), height(C))
              = 1 + max(1 + max(height(D), height(null)), 1 + max(-1, -1))
              = 1 + max(1 + max(0, -1), 0)
              = 1 + max(1 + 0, 0)
              = 1 + max(1, 0)
              = 1 + 1 = 2 ✓
    
    Tree 3 (skewed):
        A
         \
          B
           \
            C
    height(A) = 1 + max(-1, height(B))
              = 1 + max(-1, 1 + max(-1, height(C)))
              = 1 + max(-1, 1 + max(-1, 0))
              = 1 + max(-1, 1 + 0)
              = 1 + 1 = 2 ✓
*/

Base Case Matters!

The choice of base case (-1 for empty tree) isn't arbitrary—it ensures the arithmetic works correctly. If we used 0 for empty trees, a single node would have height 1 (since 1 + max(0, 0) = 1), which is wrong by the edges convention. Always verify your base case produces correct results for simple trees.

Computing Node Depth

Definition: The depth of a node is the number of edges from the root to that node. The root has depth 0, its children have depth 1, and so on.

Recursive Insight:

Unlike size and height, depth requires information from ancestors, not descendants. This means we use the Accumulate Pattern, passing the current depth down the tree.

Key Distinction:

Height is computed bottom-up (combine pattern)
Depth is computed top-down (accumulate pattern)

Node Depth Algorithms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
 * Finds the depth of a specific node in a binary tree.
 * 
 * Time Complexity: O(n) - may need to visit all nodes
 * Space Complexity: O(h) - recursion depth
 * 
 * @param root - Root of the tree
 * @param target - The node whose depth we want
 * @returns Depth of the node, or -1 if not found
 */
function findDepth(
    root: TreeNode | null, 
    target: TreeNode
): number {
    return findDepthHelper(root, target, 0);
}
 
function findDepthHelper(
    node: TreeNode | null, 
    target: TreeNode, 
    currentDepth: number  // Accumulated depth passed down
): number {
    // Base case: node not found on this path
    if (node === null) {
        return -1;
    }
    
    // Check if this is the target node
    if (node === target) {
        return currentDepth;
    }
    
    // Search in left subtree with incremented depth
    const leftResult = findDepthHelper(node.left, target, currentDepth + 1);
    if (leftResult !== -1) {
        return leftResult;
    }
    
    // If not in left, search in right subtree
    return findDepthHelper(node.right, target, currentDepth + 1);
}
 
/**
 * Alternative: Assign depths to ALL nodes in the tree.
 * Useful when you need depths of multiple nodes.
 * 
 * Uses the accumulate pattern to pass depth down to every node.
 */
function assignAllDepths(
    node: TreeNode | null, 
    depth: number,
    result: Map<TreeNode, number>
): void {
    if (node === null) return;
    
    // Record this node's depth
    result.set(node, depth);
    
    // Recursively assign depths to children (depth + 1)
    assignAllDepths(node.left, depth + 1, result);
    assignAllDepths(node.right, depth + 1, result);
}
 
// Usage:
// const depths = new Map<TreeNode, number>();
// assignAllDepths(root, 0, depths);
// console.log(depths.get(someNode));  // Returns depth of someNode

Height vs Depth

Height is about looking down (how far to deepest descendant). Depth is about looking up (how far from root). Height uses the combine pattern (bottom-up). Depth uses the accumulate pattern (top-down). The height of the tree equals the maximum depth of any node.

Counting Leaf Nodes

Definition: A leaf node is a node with no children (both left and right are null). The leaf count is the number of such nodes.

Recursive Insight:

The leaf count of a tree is:

0 if the tree is empty
1 if the node is a leaf (both children null)
leafCount(left) + leafCount(right) if the node has children

This is a variant of the combine pattern where leaf nodes are the actual contributors, and internal nodes merely aggregate.

Count Leaf Nodes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * Counts the number of leaf nodes in a binary tree.
 * A leaf node has no children (both left and right are null).
 * 
 * Time Complexity: O(n) - visits each node exactly once
 * Space Complexity: O(h) - recursion depth equals tree height
 * 
 * @param node - Root of the tree (or subtree)
 * @returns Number of leaf nodes
 */
function countLeaves(node: TreeNode | null): number {
    // Base case 1: empty tree has no leaves
    if (node === null) {
        return 0;
    }
    
    // Base case 2: leaf node (no children) counts as 1
    if (node.left === null && node.right === null) {
        return 1;
    }
    
    // Recursive case: sum of leaves in left and right subtrees
    // Note: interior nodes don't add to the count directly
    return countLeaves(node.left) + countLeaves(node.right);
}
 
// Example:
/*
          1          ← Not a leaf (has children)
         / \
        2   3        ← 3 is a leaf (no children)
       / \
      4   5          ← Both are leaves (no children)
    
    countLeaves(1) = countLeaves(2) + countLeaves(3)
                   = (countLeaves(4) + countLeaves(5)) + 1
                   = (1 + 1) + 1
                   = 3 ✓
*/
 
/**
 * Alternative: Count internal (non-leaf) nodes
 */
function countInternalNodes(node: TreeNode | null): number {
    // Empty tree or leaf node: not an internal node
    if (node === null || (node.left === null && node.right === null)) {
        return 0;
    }
    
    // This is an internal node, count it plus children's internal nodes
    return 1 + countInternalNodes(node.left) + countInternalNodes(node.right);
}
 
// Property: size = countLeaves + countInternalNodes

A Useful Property

In a full binary tree (every node has 0 or 2 children), the number of leaf nodes equals the number of internal nodes plus 1. This is a fundamental property you can derive from recursion: L = I + 1.

Computing Sum of All Values

Definition: For a tree of numeric values, the sum is the total of all node values.

Recursive Insight:

The sum of a tree is:

0 if the tree is empty
node's value + sum of left subtree + sum of right subtree

This is the quintessential combine pattern, identical in structure to size but contributing the node's value instead of 1.

Tree Sum Algorithm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
 * Computes the sum of all node values in a binary tree.
 * 
 * Time Complexity: O(n) - visits each node exactly once
 * Space Complexity: O(h) - recursion depth equals tree height
 * 
 * @param node - Root of the tree (or subtree)
 * @returns Sum of all values in the tree
 */
function treeSum(node: TreeNode<number> | null): number {
    // Base case: empty tree contributes 0 to sum
    if (node === null) {
        return 0;
    }
    
    // Recursive case: this value + left sum + right sum
    return node.value + treeSum(node.left) + treeSum(node.right);
}
 
// Example:
/*
          5
         / \
        3   8
       / \   \
      1   4   10
    
    treeSum = 5 + 3 + 8 + 1 + 4 + 10 = 31
    
    Computed recursively:
    sum(5) = 5 + sum(3) + sum(8)
           = 5 + (3 + sum(1) + sum(4)) + (8 + sum(null) + sum(10))
           = 5 + (3 + 1 + 4) + (8 + 0 + 10)
           = 5 + 8 + 18 = 31 ✓
*/
 
/**
 * Generalized: Compute any aggregate function over tree values
 */
type AggregateFunction<T, R> = (current: T, leftResult: R, rightResult: R) => R;
 
function treeAggregate<T, R>(
    node: TreeNode<T> | null,
    identity: R,                    // Value for empty tree
    aggregate: AggregateFunction<T, R>   // How to combine
): R {
    if (node === null) {
        return identity;
    }
    
    const leftResult = treeAggregate(node.left, identity, aggregate);
    const rightResult = treeAggregate(node.right, identity, aggregate);
    
    return aggregate(node.value, leftResult, rightResult);
}
 
// Usage examples:
// Sum
// treeAggregate(root, 0, (val, left, right) => val + left + right);
 
// Product
// treeAggregate(root, 1, (val, left, right) => val * left * right);
 
// Max
// treeAggregate(root, -Infinity, (val, left, right) => Math.max(val, left, right));
 
// Count
// treeAggregate(root, 0, (val, left, right) => 1 + left + right);

Finding Maximum and Minimum Values

Definition: Find the maximum (or minimum) value among all nodes in the tree.

Recursive Insight:

The maximum value in a tree is:

-∞ if the tree is empty (so it loses any comparison)
max(node's value, max value in left subtree, max value in right subtree)

The minimum uses the same structure with min and +∞ as the base case.

Critical Base Case Choice:

Using -∞ for empty trees in max (and +∞ for min) ensures the identity property: max(x, -∞) = x. This allows the recursion to work correctly when a node has only one child.

Max and Min Values
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/**
 * Finds the maximum value in a binary tree.
 * 
 * Time Complexity: O(n) - must check every node
 * Space Complexity: O(h) - recursion depth
 * 
 * Note: For a BST, maximum can be found in O(h) by going right.
 * This general algorithm works for any binary tree.
 * 
 * @param node - Root of the tree
 * @returns Maximum value, or -Infinity for empty tree
 */
function findMax(node: TreeNode<number> | null): number {
    // Base case: empty tree returns -Infinity
    // (so it always loses when compared with actual values)
    if (node === null) {
        return -Infinity;
    }
    
    // Find max in subtrees
    const leftMax = findMax(node.left);
    const rightMax = findMax(node.right);
    
    // Maximum is the greatest of: this value, left max, right max
    return Math.max(node.value, leftMax, rightMax);
}
 
/**
 * Finds the minimum value in a binary tree.
 */
function findMin(node: TreeNode<number> | null): number {
    // Base case: empty tree returns +Infinity
    if (node === null) {
        return Infinity;
    }
    
    const leftMin = findMin(node.left);
    const rightMin = findMin(node.right);
    
    return Math.min(node.value, leftMin, rightMin);
}
 
/**
 * Alternative: Find the node (not just value) containing maximum
 */
function findMaxNode(node: TreeNode<number> | null): TreeNode<number> | null {
    if (node === null) {
        return null;
    }
    
    // Find max nodes in subtrees
    const leftMaxNode = findMaxNode(node.left);
    const rightMaxNode = findMaxNode(node.right);
    
    // Determine which node has the maximum value
    let maxNode = node;
    
    if (leftMaxNode !== null && leftMaxNode.value > maxNode.value) {
        maxNode = leftMaxNode;
    }
    if (rightMaxNode !== null && rightMaxNode.value > maxNode.value) {
        maxNode = rightMaxNode;
    }
    
    return maxNode;
}

Checking Tree Properties (Predicates)

Many tree algorithms answer yes/no questions: Is the tree balanced? Are all values positive? Is it a BST? These are computed using recursive predicates.

Pattern: Recursive Predicate

For predicates (boolean-returning functions), the combine pattern uses logical operators:

AND-based: property must hold for all nodes
OR-based: property must hold for at least one node

Base Case for Predicates:

AND predicates return true for empty tree (vacuously true)
OR predicates return false for empty tree (no node satisfies condition)

Tree Predicate Algorithms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
 * Checks if all values in tree are positive.
 * Uses AND logic: must hold for every node.
 */
function allPositive(node: TreeNode<number> | null): boolean {
    // Base case: empty tree is vacuously all-positive
    if (node === null) {
        return true;
    }
    
    // This node must be positive AND both subtrees must be all-positive
    return node.value > 0 && 
           allPositive(node.left) && 
           allPositive(node.right);
}
 
/**
 * Checks if any value in tree equals target.
 * Uses OR logic: must hold for at least one node.
 */
function containsValue<T>(node: TreeNode<T> | null, target: T): boolean {
    // Base case: empty tree doesn't contain anything
    if (node === null) {
        return false;
    }
    
    // This node matches OR left subtree contains it OR right subtree contains it
    return node.value === target || 
           containsValue(node.left, target) || 
           containsValue(node.right, target);
}
 
/**
 * Checks if tree is height-balanced.
 * A tree is balanced if for every node, left and right heights differ by at most 1.
 * 
 * Naive approach: O(n²) - computes height repeatedly
 */
function isBalancedNaive(node: TreeNode | null): boolean {
    if (node === null) {
        return true;
    }
    
    const leftHeight = height(node.left);
    const rightHeight = height(node.right);
    
    // Check balance at this node AND recursively check children
    return Math.abs(leftHeight - rightHeight) <= 1 &&
           isBalancedNaive(node.left) &&
           isBalancedNaive(node.right);
}
 
/**
 * Optimized balanced check: O(n) by returning height while checking
 * Returns -2 if unbalanced, otherwise returns height
 */
function balancedHeight(node: TreeNode | null): number {
    if (node === null) {
        return -1;
    }
    
    const leftHeight = balancedHeight(node.left);
    if (leftHeight === -2) return -2;  // Left subtree unbalanced
    
    const rightHeight = balancedHeight(node.right);
    if (rightHeight === -2) return -2;  // Right subtree unbalanced
    
    // Check balance at this node
    if (Math.abs(leftHeight - rightHeight) > 1) {
        return -2;  // Unbalanced
    }
    
    return 1 + Math.max(leftHeight, rightHeight);
}
 
function isBalanced(node: TreeNode | null): boolean {
    return balancedHeight(node) !== -2;
}

Short-Circuit Evaluation

AND predicates can short-circuit: if the current node fails, no need to check children. OR predicates can also short-circuit: if found in left subtree, no need to search right. This improves average-case performance for unbalanced trees or early matches.

Summary: Your Recursive Tree Toolkit

You now have a comprehensive toolkit for computing tree properties recursively. Let's consolidate what we've learned:

Recursive Tree Property Computations
Property	Pattern	Base Case	Time	Space
Size	Combine	0 (empty has no nodes)	O(n)	O(h)
Height	Combine	-1 (empty tree)	O(n)	O(h)
Node Depth	Accumulate	Found or not found	O(n)	O(h)
Leaf Count	Combine	0 (empty), 1 (leaf)	O(n)	O(h)
Sum/Product	Combine	Identity value (0/1)	O(n)	O(h)
Max/Min	Combine	±Infinity	O(n)	O(h)
All Satisfy	Combine (AND)	true (vacuous)	O(n)	O(h)
Any Satisfies	Combine (OR)	false	O(n)	O(h)
Is Balanced	Combine + Early Exit	true/-1	O(n)	O(h)

Key Takeaways

•Choose the right base case — The base case must be the identity element for your combining operation.
•All properties are O(n) time — We must visit each node at least once to compute any global property.
•Space is O(h) — The call stack depth equals the tree height, ranging from O(log n) to O(n).
•Combine pattern dominates — Most tree properties use bottom-up combination of subtree results.
•Optimize by multiple returns — Compute multiple properties in one pass (like balanced check returning height).
•Predicates use short-circuit logic — AND/OR predicates can terminate early when result is determined.

What's Next:

With these foundational algorithms mastered, we move to the final page of this module: Thinking with Subtrees. You'll learn advanced techniques for solving complex tree problems by decomposing them into subtree subproblems, building on everything you've learned to tackle sophisticated tree challenges.

Page Complete

You can now compute any standard tree property recursively. These algorithms form the building blocks for more complex tree operations. Practice implementing them until the patterns become second nature—they'll appear again and again in tree problems.

Computing Height, Size, and Properties Recursively

From Theory to Practice

For each property, we'll examine:

The definition — What exactly are we computing?
The recursive insight — How does the property decompose?
The algorithm — Clean, production-quality code
Complexity analysis — Time and space costs
Common pitfalls — Mistakes to avoid

What You Will Learn

Computing Tree Size

Definition: The size of a tree is the total number of nodes it contains.

Recursive Insight:

The size of a tree is:

0 if the tree is empty
1 (for the root) + size of left subtree + size of right subtree

This is a classic application of the Combine Pattern: get results from subtrees, combine with current node's contribution.

The Elegance:

Notice how the algorithm reads almost like the definition. We're not iterating, not counting, not managing any state. We simply declare what size means and let recursion compute it.

Tree Size Algorithm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Computes the total number of nodes in a binary tree.
 * 
 * Time Complexity: O(n) - visits each node exactly once
 * Space Complexity: O(h) - call stack depth equals tree height
 *     - Best case (balanced): O(log n)
 *     - Worst case (skewed): O(n)
 * 
 * @param node - Root of the tree (or subtree)
 * @returns Number of nodes in the tree
 */
function size(node: TreeNode | null): number {
    // Base case: empty tree has 0 nodes
    if (node === null) {
        return 0;
    }
    
    // Recursive case: this node (1) + left subtree + right subtree
    const leftSize = size(node.left);
    const rightSize = size(node.right);
    
    return 1 + leftSize + rightSize;
}
 
// Alternate compact form (same logic, fewer lines)
function sizeCompact(node: TreeNode | null): number {
    return node === null ? 0 : 1 + sizeCompact(node.left) + sizeCompact(node.right);
}
 
// Example usage:
/*
        1
       / \
      2   3
     / \
    4   5
 
    size(root) → 5
    
    Trace:
    size(1) = 1 + size(2) + size(3)
            = 1 + (1 + size(4) + size(5)) + (1 + size(null) + size(null))
            = 1 + (1 + (1+0+0) + (1+0+0)) + (1 + 0 + 0)
            = 1 + (1 + 1 + 1) + 1
            = 1 + 3 + 1 = 5
*/

Understanding the Complexity

Computing Tree Height

Definition: The height of a tree is the length of the longest path from the root to any leaf, measured in edges.

Convention Note: Some sources measure height in nodes (not edges), making the height of a single-node tree 1 instead of 0. We use the edges convention, which means:

Empty tree: height = -1
Single node: height = 0
Root with one child: height = 1

Recursive Insight:

The height of a tree is:

-1 if the tree is empty
0 if the tree is a single node (both children null)
1 + max(height of left subtree, height of right subtree)

The longest path must go through the root (since the root is on all paths) and extend through whichever child's subtree is taller.

Tree Height Algorithm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * Computes the height of a binary tree (longest root-to-leaf path in edges).
 * 
 * Time Complexity: O(n) - visits each node exactly once
 * Space Complexity: O(h) - recursion depth equals tree height
 * 
 * Convention:
 *   - Empty tree: height = -1
 *   - Single node: height = 0
 *   - Each level adds 1 to height
 * 
 * @param node - Root of the tree (or subtree)
 * @returns Height of the tree
 */
function height(node: TreeNode | null): number {
    // Base case: empty tree has height -1
    // (This makes single-node trees have height 0, which is correct)
    if (node === null) {
        return -1;
    }
    
    // Recursive case: 1 (for this edge) + max child height
    const leftHeight = height(node.left);
    const rightHeight = height(node.right);
    
    return 1 + Math.max(leftHeight, rightHeight);
}
 
// Example traces:
/*
    Tree 1 (single node):
        A
    height(A) = 1 + max(-1, -1) = 1 + (-1) = 0 ✓
    
    Tree 2 (balanced):
          A
         / \
        B   C
       /
      D
    height(A) = 1 + max(height(B), height(C))
              = 1 + max(1 + max(height(D), height(null)), 1 + max(-1, -1))
              = 1 + max(1 + max(0, -1), 0)
              = 1 + max(1 + 0, 0)
              = 1 + max(1, 0)
              = 1 + 1 = 2 ✓
    
    Tree 3 (skewed):
        A
         \
          B
           \
            C
    height(A) = 1 + max(-1, height(B))
              = 1 + max(-1, 1 + max(-1, height(C)))
              = 1 + max(-1, 1 + max(-1, 0))
              = 1 + max(-1, 1 + 0)
              = 1 + 1 = 2 ✓
*/

Base Case Matters!

Computing Node Depth

Definition: The depth of a node is the number of edges from the root to that node. The root has depth 0, its children have depth 1, and so on.

Recursive Insight:

Unlike size and height, depth requires information from ancestors, not descendants. This means we use the Accumulate Pattern, passing the current depth down the tree.

Key Distinction:

Height is computed bottom-up (combine pattern)
Depth is computed top-down (accumulate pattern)

Node Depth Algorithms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
 * Finds the depth of a specific node in a binary tree.
 * 
 * Time Complexity: O(n) - may need to visit all nodes
 * Space Complexity: O(h) - recursion depth
 * 
 * @param root - Root of the tree
 * @param target - The node whose depth we want
 * @returns Depth of the node, or -1 if not found
 */
function findDepth(
    root: TreeNode | null, 
    target: TreeNode
): number {
    return findDepthHelper(root, target, 0);
}
 
function findDepthHelper(
    node: TreeNode | null, 
    target: TreeNode, 
    currentDepth: number  // Accumulated depth passed down
): number {
    // Base case: node not found on this path
    if (node === null) {
        return -1;
    }
    
    // Check if this is the target node
    if (node === target) {
        return currentDepth;
    }
    
    // Search in left subtree with incremented depth
    const leftResult = findDepthHelper(node.left, target, currentDepth + 1);
    if (leftResult !== -1) {
        return leftResult;
    }
    
    // If not in left, search in right subtree
    return findDepthHelper(node.right, target, currentDepth + 1);
}
 
/**
 * Alternative: Assign depths to ALL nodes in the tree.
 * Useful when you need depths of multiple nodes.
 * 
 * Uses the accumulate pattern to pass depth down to every node.
 */
function assignAllDepths(
    node: TreeNode | null, 
    depth: number,
    result: Map<TreeNode, number>
): void {
    if (node === null) return;
    
    // Record this node's depth
    result.set(node, depth);
    
    // Recursively assign depths to children (depth + 1)
    assignAllDepths(node.left, depth + 1, result);
    assignAllDepths(node.right, depth + 1, result);
}
 
// Usage:
// const depths = new Map<TreeNode, number>();
// assignAllDepths(root, 0, depths);
// console.log(depths.get(someNode));  // Returns depth of someNode

Height vs Depth

Counting Leaf Nodes

Definition: A leaf node is a node with no children (both left and right are null). The leaf count is the number of such nodes.

Recursive Insight:

The leaf count of a tree is:

0 if the tree is empty
1 if the node is a leaf (both children null)
leafCount(left) + leafCount(right) if the node has children

This is a variant of the combine pattern where leaf nodes are the actual contributors, and internal nodes merely aggregate.

Count Leaf Nodes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * Counts the number of leaf nodes in a binary tree.
 * A leaf node has no children (both left and right are null).
 * 
 * Time Complexity: O(n) - visits each node exactly once
 * Space Complexity: O(h) - recursion depth equals tree height
 * 
 * @param node - Root of the tree (or subtree)
 * @returns Number of leaf nodes
 */
function countLeaves(node: TreeNode | null): number {
    // Base case 1: empty tree has no leaves
    if (node === null) {
        return 0;
    }
    
    // Base case 2: leaf node (no children) counts as 1
    if (node.left === null && node.right === null) {
        return 1;
    }
    
    // Recursive case: sum of leaves in left and right subtrees
    // Note: interior nodes don't add to the count directly
    return countLeaves(node.left) + countLeaves(node.right);
}
 
// Example:
/*
          1          ← Not a leaf (has children)
         / \
        2   3        ← 3 is a leaf (no children)
       / \
      4   5          ← Both are leaves (no children)
    
    countLeaves(1) = countLeaves(2) + countLeaves(3)
                   = (countLeaves(4) + countLeaves(5)) + 1
                   = (1 + 1) + 1
                   = 3 ✓
*/
 
/**
 * Alternative: Count internal (non-leaf) nodes
 */
function countInternalNodes(node: TreeNode | null): number {
    // Empty tree or leaf node: not an internal node
    if (node === null || (node.left === null && node.right === null)) {
        return 0;
    }
    
    // This is an internal node, count it plus children's internal nodes
    return 1 + countInternalNodes(node.left) + countInternalNodes(node.right);
}
 
// Property: size = countLeaves + countInternalNodes

A Useful Property

In a full binary tree (every node has 0 or 2 children), the number of leaf nodes equals the number of internal nodes plus 1. This is a fundamental property you can derive from recursion: L = I + 1.

Computing Sum of All Values

Definition: For a tree of numeric values, the sum is the total of all node values.

Recursive Insight:

The sum of a tree is:

0 if the tree is empty
node's value + sum of left subtree + sum of right subtree

This is the quintessential combine pattern, identical in structure to size but contributing the node's value instead of 1.

Tree Sum Algorithm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
 * Computes the sum of all node values in a binary tree.
 * 
 * Time Complexity: O(n) - visits each node exactly once
 * Space Complexity: O(h) - recursion depth equals tree height
 * 
 * @param node - Root of the tree (or subtree)
 * @returns Sum of all values in the tree
 */
function treeSum(node: TreeNode<number> | null): number {
    // Base case: empty tree contributes 0 to sum
    if (node === null) {
        return 0;
    }
    
    // Recursive case: this value + left sum + right sum
    return node.value + treeSum(node.left) + treeSum(node.right);
}
 
// Example:
/*
          5
         / \
        3   8
       / \   \
      1   4   10
    
    treeSum = 5 + 3 + 8 + 1 + 4 + 10 = 31
    
    Computed recursively:
    sum(5) = 5 + sum(3) + sum(8)
           = 5 + (3 + sum(1) + sum(4)) + (8 + sum(null) + sum(10))
           = 5 + (3 + 1 + 4) + (8 + 0 + 10)
           = 5 + 8 + 18 = 31 ✓
*/
 
/**
 * Generalized: Compute any aggregate function over tree values
 */
type AggregateFunction<T, R> = (current: T, leftResult: R, rightResult: R) => R;
 
function treeAggregate<T, R>(
    node: TreeNode<T> | null,
    identity: R,                    // Value for empty tree
    aggregate: AggregateFunction<T, R>   // How to combine
): R {
    if (node === null) {
        return identity;
    }
    
    const leftResult = treeAggregate(node.left, identity, aggregate);
    const rightResult = treeAggregate(node.right, identity, aggregate);
    
    return aggregate(node.value, leftResult, rightResult);
}
 
// Usage examples:
// Sum
// treeAggregate(root, 0, (val, left, right) => val + left + right);
 
// Product
// treeAggregate(root, 1, (val, left, right) => val * left * right);
 
// Max
// treeAggregate(root, -Infinity, (val, left, right) => Math.max(val, left, right));
 
// Count
// treeAggregate(root, 0, (val, left, right) => 1 + left + right);

Finding Maximum and Minimum Values

Definition: Find the maximum (or minimum) value among all nodes in the tree.

Recursive Insight:

The maximum value in a tree is:

-∞ if the tree is empty (so it loses any comparison)
max(node's value, max value in left subtree, max value in right subtree)

The minimum uses the same structure with min and +∞ as the base case.

Critical Base Case Choice:

Using -∞ for empty trees in max (and +∞ for min) ensures the identity property: max(x, -∞) = x. This allows the recursion to work correctly when a node has only one child.

Max and Min Values
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/**
 * Finds the maximum value in a binary tree.
 * 
 * Time Complexity: O(n) - must check every node
 * Space Complexity: O(h) - recursion depth
 * 
 * Note: For a BST, maximum can be found in O(h) by going right.
 * This general algorithm works for any binary tree.
 * 
 * @param node - Root of the tree
 * @returns Maximum value, or -Infinity for empty tree
 */
function findMax(node: TreeNode<number> | null): number {
    // Base case: empty tree returns -Infinity
    // (so it always loses when compared with actual values)
    if (node === null) {
        return -Infinity;
    }
    
    // Find max in subtrees
    const leftMax = findMax(node.left);
    const rightMax = findMax(node.right);
    
    // Maximum is the greatest of: this value, left max, right max
    return Math.max(node.value, leftMax, rightMax);
}
 
/**
 * Finds the minimum value in a binary tree.
 */
function findMin(node: TreeNode<number> | null): number {
    // Base case: empty tree returns +Infinity
    if (node === null) {
        return Infinity;
    }
    
    const leftMin = findMin(node.left);
    const rightMin = findMin(node.right);
    
    return Math.min(node.value, leftMin, rightMin);
}
 
/**
 * Alternative: Find the node (not just value) containing maximum
 */
function findMaxNode(node: TreeNode<number> | null): TreeNode<number> | null {
    if (node === null) {
        return null;
    }
    
    // Find max nodes in subtrees
    const leftMaxNode = findMaxNode(node.left);
    const rightMaxNode = findMaxNode(node.right);
    
    // Determine which node has the maximum value
    let maxNode = node;
    
    if (leftMaxNode !== null && leftMaxNode.value > maxNode.value) {
        maxNode = leftMaxNode;
    }
    if (rightMaxNode !== null && rightMaxNode.value > maxNode.value) {
        maxNode = rightMaxNode;
    }
    
    return maxNode;
}

Checking Tree Properties (Predicates)

Many tree algorithms answer yes/no questions: Is the tree balanced? Are all values positive? Is it a BST? These are computed using recursive predicates.

Pattern: Recursive Predicate

For predicates (boolean-returning functions), the combine pattern uses logical operators:

AND-based: property must hold for all nodes
OR-based: property must hold for at least one node

Base Case for Predicates:

AND predicates return true for empty tree (vacuously true)
OR predicates return false for empty tree (no node satisfies condition)

Tree Predicate Algorithms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
 * Checks if all values in tree are positive.
 * Uses AND logic: must hold for every node.
 */
function allPositive(node: TreeNode<number> | null): boolean {
    // Base case: empty tree is vacuously all-positive
    if (node === null) {
        return true;
    }
    
    // This node must be positive AND both subtrees must be all-positive
    return node.value > 0 && 
           allPositive(node.left) && 
           allPositive(node.right);
}
 
/**
 * Checks if any value in tree equals target.
 * Uses OR logic: must hold for at least one node.
 */
function containsValue<T>(node: TreeNode<T> | null, target: T): boolean {
    // Base case: empty tree doesn't contain anything
    if (node === null) {
        return false;
    }
    
    // This node matches OR left subtree contains it OR right subtree contains it
    return node.value === target || 
           containsValue(node.left, target) || 
           containsValue(node.right, target);
}
 
/**
 * Checks if tree is height-balanced.
 * A tree is balanced if for every node, left and right heights differ by at most 1.
 * 
 * Naive approach: O(n²) - computes height repeatedly
 */
function isBalancedNaive(node: TreeNode | null): boolean {
    if (node === null) {
        return true;
    }
    
    const leftHeight = height(node.left);
    const rightHeight = height(node.right);
    
    // Check balance at this node AND recursively check children
    return Math.abs(leftHeight - rightHeight) <= 1 &&
           isBalancedNaive(node.left) &&
           isBalancedNaive(node.right);
}
 
/**
 * Optimized balanced check: O(n) by returning height while checking
 * Returns -2 if unbalanced, otherwise returns height
 */
function balancedHeight(node: TreeNode | null): number {
    if (node === null) {
        return -1;
    }
    
    const leftHeight = balancedHeight(node.left);
    if (leftHeight === -2) return -2;  // Left subtree unbalanced
    
    const rightHeight = balancedHeight(node.right);
    if (rightHeight === -2) return -2;  // Right subtree unbalanced
    
    // Check balance at this node
    if (Math.abs(leftHeight - rightHeight) > 1) {
        return -2;  // Unbalanced
    }
    
    return 1 + Math.max(leftHeight, rightHeight);
}
 
function isBalanced(node: TreeNode | null): boolean {
    return balancedHeight(node) !== -2;
}

Short-Circuit Evaluation

Summary: Your Recursive Tree Toolkit

You now have a comprehensive toolkit for computing tree properties recursively. Let's consolidate what we've learned:

Recursive Tree Property Computations
Property	Pattern	Base Case	Time	Space
Size	Combine	0 (empty has no nodes)	O(n)	O(h)
Height	Combine	-1 (empty tree)	O(n)	O(h)
Node Depth	Accumulate	Found or not found	O(n)	O(h)
Leaf Count	Combine	0 (empty), 1 (leaf)	O(n)	O(h)
Sum/Product	Combine	Identity value (0/1)	O(n)	O(h)
Max/Min	Combine	±Infinity	O(n)	O(h)
All Satisfy	Combine (AND)	true (vacuous)	O(n)	O(h)
Any Satisfies	Combine (OR)	false	O(n)	O(h)
Is Balanced	Combine + Early Exit	true/-1	O(n)	O(h)

Key Takeaways

•Choose the right base case — The base case must be the identity element for your combining operation.
•All properties are O(n) time — We must visit each node at least once to compute any global property.
•Space is O(h) — The call stack depth equals the tree height, ranging from O(log n) to O(n).
•Combine pattern dominates — Most tree properties use bottom-up combination of subtree results.
•Optimize by multiple returns — Compute multiple properties in one pass (like balanced check returning height).
•Predicates use short-circuit logic — AND/OR predicates can terminate early when result is determined.

What's Next:

Page Complete