Data Structures & AlgorithmsCommon Tree Patterns & Problem Types

Common Tree Patterns & Problem Types

LevelIntermediate

Duration120 mins

TopicCommon Tree Patterns & Problem Types

4 / 5

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: 1 / 2 3 / 4 5 / 6 7 Diameter path: 4 \to 2 \to 5 \to 6 (or 4 \to 2 \to 5 \to 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: 1 / 2 3 / 4 5 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 \to 0 \to 2 \to 2 \to 3 Final diameter = 3 (path: 4 \to 2 \to 1 \to 3 or 5 \to 2 \to 1 \to 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 \to call it A From A, find the farthest node \to call it B The path A \to 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.

Related Problems

The diameter algorithm pattern extends to several related problems. Recognizing these variations helps you apply the pattern flexibly. 1. Longest Univalue Path: Find the longest path where all nodes have the same value. Same algorithm, but we only 'extend' the path through edges connecting equal values. 2. Tree Radius and Center: The radius is half the diameter (the minimum max-distance from any node to all others). The center is the node(s) achieving this minimum. Finding the center involves finding the diameter path and taking its midpoint. 3. Longest Zigzag Path: Find the longest path alternating left-right-left-right. Track two values per node: max zigzag ending in left, max zigzag ending in right. 4. Maximum Width of Binary Tree: Different from diameter — this is the maximum number of nodes at any level. Uses BFS with position indexing.

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)

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
/**
 * Finds the longest path where all nodes have the same value.
 * 
 * Same as diameter, but we only extend paths through matching values.
 * 
 * Time: O(n)
 * Space: O(h)
 */
function longestUnivaluePath(root: TreeNode | null): number {
    let maxPath = 0;
    
    /**
     * Returns the length of the longest single-arm path from this node
     * downward that has all the same value as the parent.
     * 
     * @param node Current node
     * @param parentVal Value of the parent (to match against)
     */
    function arrowLength(node: TreeNode | null, parentVal: number): number {
        if (node === null) {
            return 0;
        }
        
        // Recursively get arrow lengths from children
        const leftArrow = arrowLength(node.left, node.val);
        const rightArrow = arrowLength(node.right, node.val);
        
        // Path through this node (if both sides have same value)
        // This is the "diameter" for univalue paths
        maxPath = Math.max(maxPath, leftArrow + rightArrow);
        
        // Can we extend to parent?
        if (node.val === parentVal) {
            // Return longest arm + 1 (edge to parent)
            return 1 + Math.max(leftArrow, rightArrow);
        } else {
            // Value doesn't match parent, can't extend
            return 0;
        }
    }
    
    if (root !== null) {
        arrowLength(root, root.val);  // Use root's value as initial match
    }
    return maxPath;
}

4 / 5

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.

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)

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; }

/** * 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 }

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

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

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 }

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; }

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; }

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)

/** * Finds the longest path where all nodes have the same value. * * Same as diameter, but we only extend paths through matching values. * * Time: O(n) * Space: O(h) */ function longestUnivaluePath(root: TreeNode | null): number { let maxPath = 0; /** * Returns the length of the longest single-arm path from this node * downward that has all the same value as the parent. * * @param node Current node * @param parentVal Value of the parent (to match against) */ function arrowLength(node: TreeNode | null, parentVal: number): number { if (node === null) { return 0; } // Recursively get arrow lengths from children const leftArrow = arrowLength(node.left, node.val); const rightArrow = arrowLength(node.right, node.val); // Path through this node (if both sides have same value) // This is the "diameter" for univalue paths maxPath = Math.max(maxPath, leftArrow + rightArrow); // Can we extend to parent? if (node.val === parentVal) { // Return longest arm + 1 (edge to parent) return 1 + Math.max(leftArrow, rightArrow); } else { // Value doesn't match parent, can't extend return 0; } } if (root !== null) { arrowLength(root, root.val); // Use root's value as initial match } return maxPath; }

Diameter of a Tree

The Longest Journey — Finding Maximum Distance in Trees

Understanding Tree Diameter

The Key Insight — Peak Node Analysis

The Elegant O(n) Solution

Alternative Approaches

Extension — Weighted Tree Diameter

Extension — N-ary Tree Diameter

Related Problems

There’s more to understand.

Diameter of a Tree

The Longest Journey — Finding Maximum Distance in Trees

Understanding Tree Diameter

The Key Insight — Peak Node Analysis

The Elegant O(n) Solution

Alternative Approaches

Extension — Weighted Tree Diameter

Extension — N-ary Tree Diameter

Related Problems

There’s more to understand.