Common Tree Patterns - Learning Module

Loading content...

0/276

Diameter of a Tree

The Longest Journey — Finding Maximum Distance in Trees

Imagine you're planning a hiking trail through a network of paths that form a tree structure — no loops, just branching paths. You want to know: what's the longest possible hike you could take without backtracking? Which two endpoints are furthest apart?

This is the tree diameter problem — finding the longest path between any two nodes in a tree. The diameter gives us the maximum 'spread' of the tree, a fundamental metric for understanding tree shape and behavior.

Diameter calculations appear everywhere: measuring network latency bounds, analyzing organization hierarchies, understanding compiler optimization opportunities, and even in computational biology for phylogenetic analysis. Mastering this problem teaches a crucial algorithmic pattern that applies to many tree optimization problems.

What You Will Master

By the end of this page, you will:

• Understand why diameter is non-trivial (the longest path need not pass through the root) • Master the elegant O(n) solution using depth-first search • Learn the 'return one thing, track another' pattern — a powerful tree algorithm technique • Extend the solution to weighted trees and N-ary trees • Apply diameter concepts to related problems (longest path in binary tree, tree center)

Understanding Tree Diameter

Definition:

The diameter of a tree is the length of the longest path between any two nodes. The path length is typically counted in edges (number of connections traversed), though some variants count nodes.

Key Observations:

The diameter path might not include the root: Unlike root-to-leaf paths we studied earlier, the diameter can connect any two nodes.
Endpoints are leaves: The longest path must end at leaves (if not, we could extend it further).
The path has a 'peak' node: Every diameter path has a highest (closest to root) node through which it passes — we call this the 'peak' or 'turning point'.
Uniqueness: Multiple diameter paths can exist with the same length.

Example:

Diameter path: 4 → 2 → 5 → 6 (or 4 → 2 → 5 → 7)

Length: 3 edges
Peak node: 2 (highest node on the path)
Note: This path doesn't go through the root!

Common Misconception

Many students initially think: 'find the deepest leaf on the left, the deepest on the right, add the depths.' This gives left-depth + right-depth through the root, but this is only correct if the diameter happens to pass through the root. The actual diameter might be entirely within one subtree!

Why the root-passing diameter isn't always correct:

        1              Depth through root: 2 + 1 = 3
       / \             (path: 4 → 2 → 1 → 3)
      2   3
     / \
    4   5              But consider this extended tree:
       / \
      6   7            Path 4 → 2 → 5 → 6 has length 3
                       Path 6 → 5 → 7 doesn't involve root at all!
                       The true diameter is 3 edges.

In this case, both paths have the same length, but the key insight is that we must consider diameters that peak at internal nodes, not just at the root.

The Key Insight — Peak Node Analysis

The elegant O(n) solution comes from realizing that every diameter path peaks at exactly one node. At this peak node, the diameter path comes up from one subtree and goes down into another (or the same) subtree.

Peak Node Perspective:

For any node N, the longest path that has N as its peak is: leftHeight(N) + rightHeight(N)

where height is the maximum depth of that subtree.

The Global Diameter:

The tree's diameter is the maximum of all possible peak-at-N diameters: diameter = max over all N of (leftHeight(N) + rightHeight(N))

How to compute efficiently:

As we recursively compute heights (which we need anyway), we can simultaneously track the best diameter seen so far. This gives us O(n) — visit each node once.

Visualizing the Peak:

        1              For diameter peaking at 2:
       / \             - Left height (from 4) = 1
      2   3            - Right height (from 5→6 or 5→7) = 2
     / \               - Diameter through 2 = 1 + 2 = 3
    4   5
       / \
      6   7            For diameter peaking at 1:
                       - Left height = 3 (1→2→5→6)
                       - Right height = 1 (1→3)
                       - Diameter through 1 = 3 + 1 = 4

                       Wait! 4 > 3, so the diameter through root is longer!
                       True diameter = 4 (path: 6→5→2→1→3 or 7→5→2→1→3)

This example shows why we must check all possible peaks. The actual diameter is 4 edges, and it does pass through the root.

The Recursive Structure:

For each node:

Compute height of left subtree
Compute height of right subtree
Update global diameter with (left height + right height)
Return max height for parent's calculation

The 'Return One Thing, Track Another' Pattern

This algorithm demonstrates a powerful pattern: the recursive function returns one value (height for parent's use) while updating another (global diameter). This pattern appears in many tree optimization problems: return what's needed for recursion, track the actual answer separately.

The Elegant O(n) Solution

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
interface TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
}
 
/**
 * Finds the diameter of a binary tree — the longest path between any two nodes.
 * Path length is measured in number of EDGES.
 * 
 * Key insight: At each node, the path that "peaks" here has length
 * leftHeight + rightHeight. We compute heights recursively and track
 * the maximum diameter seen as a side effect.
 * 
 * Time: O(n) - each node visited exactly once
 * Space: O(h) - recursion stack depth
 */
function diameterOfBinaryTree(root: TreeNode | null): number {
    let maxDiameter = 0;
    
    /**
     * Computes height of the subtree rooted at 'node'.
     * Height = max edges from node to any leaf in its subtree.
     * 
     * SIDE EFFECT: Updates maxDiameter if the path through this node
     * is longer than the current best.
     */
    function height(node: TreeNode | null): number {
        // Base case: null node has no height contribution
        // We return 0 because there are 0 edges from null
        if (node === null) {
            return 0;
        }
        
        // Recursively get heights of subtrees
        const leftHeight = height(node.left);
        const rightHeight = height(node.right);
        
        // The diameter that "peaks" at this node is left + right heights
        // (These are edges: 'leftHeight' edges down the left, 
        //  'rightHeight' edges down the right)
        const diameterThroughNode = leftHeight + rightHeight;
        maxDiameter = Math.max(maxDiameter, diameterThroughNode);
        
        // Return this node's height for parent's use
        // Height = 1 (edge to this node) + max height of children
        return 1 + Math.max(leftHeight, rightHeight);
    }
    
    height(root);
    return maxDiameter;
}

Walking Through an Example:

Post-order traversal (process children first):

At 4: left=0, right=0, diameter=0+0=0, return 1
At 5: left=0, right=0, diameter=0+0=0, return 1
At 2: left=1, right=1, diameter=1+1=2, return 1+max(1,1)=2
At 3: left=0, right=0, diameter=0+0=0, return 1
At 1: left=2, right=1, diameter=2+1=3, return 1+max(2,1)=3

maxDiameter updates: 0 → 0 → 2 → 2 → 3

Final diameter = 3 (path: 4 → 2 → 1 → 3 or 5 → 2 → 1 → 3)

Edges vs Nodes

Our solution counts edges. Some problems count nodes instead. If you need node count:

nodeCount = edgeCount + 1

So return maxDiameter + 1 at the end if counting nodes.

Always clarify in interviews which metric is expected!

Alternative Approaches

While the height-based approach is most elegant, understanding alternatives deepens our intuition.

Approach 1: Two BFS/DFS (for general trees)

Pick any node, find the farthest node from it using BFS → call it A
From A, find the farthest node → call it B
The path A → B is a diameter

This works because the farthest node from any node is always a diameter endpoint. Proof by contradiction: if A weren't a diameter endpoint, we could extend the diameter by going through A.

Approach 2: Returning Multiple Values

Instead of using a global variable, we can return a tuple of (height, diameter):

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
/**
 * Alternative approach: return both height and subtree diameter.
 * No global variable needed — purely functional style.
 * 
 * Returns: [height, maxDiameterInSubtree]
 */
function diameterPure(root: TreeNode | null): number {
    // Returns [height, diameter in this subtree]
    function helper(node: TreeNode | null): [number, number] {
        if (node === null) {
            return [0, 0];
        }
        
        const [leftHeight, leftDiam] = helper(node.left);
        const [rightHeight, rightDiam] = helper(node.right);
        
        // Height of this subtree
        const height = 1 + Math.max(leftHeight, rightHeight);
        
        // Diameter is max of:
        // 1. Diameter entirely in left subtree
        // 2. Diameter entirely in right subtree
        // 3. Path passing through this node (leftHeight + rightHeight)
        const diameter = Math.max(
            leftDiam,
            rightDiam,
            leftHeight + rightHeight
        );
        
        return [height, diameter];
    }
    
    return helper(root)[1];  // Return just the diameter
}

Comparison of Approaches:

Approach	Style	Pros	Cons
Global variable	Imperative	Simple, efficient	Global state, less pure
Tuple return	Functional	No side effects, no global	Slightly more allocation
Two BFS	Graph-based	Works on any tree repr	Two passes, more complex

The global variable approach is most common in interviews because it's concise. The tuple approach is preferred in production code where purity and testability matter.

Class-Based Alternative

In languages like Java/TypeScript, you can use a class with a field instead of a closure variable:

class DiameterFinder {
    private maxDiameter = 0;
    
    diameter(root: TreeNode | null): number {
        this.computeHeight(root);
        return this.maxDiameter;
    }
    
    private computeHeight(node: TreeNode | null): number { ... }
}

This is equivalent to the closure approach but more explicitly stateful.

Extension — Weighted Tree Diameter

In many real applications, edges have weights (costs, distances, latencies). The weighted diameter is the maximum sum of edge weights along any path.

The adaptation is straightforward:

Instead of counting edges (adding 1 per edge), we add the actual edge weights. The 'height' becomes the maximum weighted distance to any leaf.

Data Structure with Weights:

interface WeightedTreeNode {
    val: number;
    left: WeightedTreeNode | null;
    right: WeightedTreeNode | null;
    leftWeight: number;   // Weight of edge to left child
    rightWeight: number;  // Weight of edge to right child
}

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
interface WeightedTreeNode {
    val: number;
    left: WeightedTreeNode | null;
    right: WeightedTreeNode | null;
    leftWeight: number;
    rightWeight: number;
}
 
/**
 * Finds the maximum weighted path between any two nodes.
 * 
 * Same algorithm, but we add edge weights instead of 1.
 * 
 * Time: O(n)
 * Space: O(h)
 */
function weightedDiameter(root: WeightedTreeNode | null): number {
    let maxDiameter = 0;
    
    /**
     * Returns maximum weighted distance from this node to any leaf.
     */
    function maxDistanceToLeaf(node: WeightedTreeNode | null): number {
        if (node === null) {
            return 0;
        }
        
        // Distance through left edge + left subtree's max distance
        const leftDist = node.left !== null 
            ? node.leftWeight + maxDistanceToLeaf(node.left)
            : 0;
        
        // Distance through right edge + right subtree's max distance
        const rightDist = node.right !== null
            ? node.rightWeight + maxDistanceToLeaf(node.right)
            : 0;
        
        // Diameter passing through this node
        const diameterThroughNode = leftDist + rightDist;
        maxDiameter = Math.max(maxDiameter, diameterThroughNode);
        
        // Return max distance from this node downward
        return Math.max(leftDist, rightDist);
    }
    
    maxDistanceToLeaf(root);
    return maxDiameter;
}

Handling Negative Weights:

With negative weights, the problem becomes trickier. A longer path might have lower total weight if some edges are negative. In this case:

If we want maximum weight: might want to avoid negative edges
If we want minimum weight: negative edges are beneficial

The 'max with 0' trick from maximum path sum applies:

// If including a subtree hurts our total, skip it
const leftDist = Math.max(0, node.leftWeight + maxDistanceToLeaf(node.left));

This ensures we never degrade our path by including a negative-sum branch.

Extension — N-ary Tree Diameter

For N-ary trees (trees where nodes can have any number of children), the diameter concept is the same, but we need to consider multiple children.

Key Insight:

The diameter through a node is the sum of the two longest paths to any descendants. With multiple children, we need to find the two highest subtrees.

Algorithm:

Recursively compute heights of all children
The diameter through this node = sum of two largest child heights
Return max child height + 1 for parent's use

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
interface NaryTreeNode {
    val: number;
    children: NaryTreeNode[];
}
 
/**
 * Finds the diameter of an N-ary tree.
 * 
 * Key insight: The diameter through a node uses the TWO longest
 * downward paths. We need to find the two highest subtrees.
 * 
 * Time: O(n)
 * Space: O(h)
 */
function naryTreeDiameter(root: NaryTreeNode | null): number {
    let maxDiameter = 0;
    
    function height(node: NaryTreeNode | null): number {
        if (node === null || node.children.length === 0) {
            return 0;
        }
        
        // Get heights of all children
        const childHeights: number[] = [];
        for (const child of node.children) {
            childHeights.push(1 + height(child));  // +1 for edge to child
        }
        
        // Sort descending to get the two largest
        childHeights.sort((a, b) => b - a);
        
        // Diameter through this node = sum of two largest heights
        // If only one child, the second "largest" is 0
        const firstMax = childHeights[0] || 0;
        const secondMax = childHeights[1] || 0;
        const diameterThroughNode = firstMax + secondMax;
        maxDiameter = Math.max(maxDiameter, diameterThroughNode);
        
        // Return max height for parent's use
        return firstMax;
    }
    
    height(root);
    return maxDiameter;
}
 
/**
 * Optimized version: find two largest without sorting
 * (O(k) instead of O(k log k) for k children)
 */
function naryTreeDiameterOptimized(root: NaryTreeNode | null): number {
    let maxDiameter = 0;
    
    function height(node: NaryTreeNode | null): number {
        if (node === null) return 0;
        
        // Find two largest child heights in O(k) time
        let max1 = 0, max2 = 0;
        for (const child of node.children) {
            const h = 1 + height(child);
            if (h > max1) {
                max2 = max1;
                max1 = h;
            } else if (h > max2) {
                max2 = h;
            }
        }
        
        maxDiameter = Math.max(maxDiameter, max1 + max2);
        return max1;
    }
    
    height(root);
    return maxDiameter;
}

Why Two Largest?

A path can enter a node from one subtree and exit through another. To maximize the path length through this node, we want the two longest 'arms' — the two subtrees with maximum depth. The third-longest, fourth-longest, etc. don't contribute to any diameter path through this node.

Diameter-Related Problems
Problem	What to Track	Key Modification	Complexity
Standard Diameter	Height per subtree	Sum of two largest	O(n)
Weighted Diameter	Weighted depth	Add edge weights	O(n)
Longest Univalue Path	Same-value height	Only extend if values match	O(n)
Tree Radius/Center	Diameter endpoints	Find midpoint of diameter	O(n)
Longest Zigzag	Left-ending, Right-ending	Alternate extension	O(n)