Tree Diameter and Path Length

Design Pattern: Both challenges require a "Global Update" within a post-order DFS. A global variable tracks the final answer while the recursive function returns a "single-path" maximum value for the parent node to utilize.

Diameter of Binary Tree (LeetCode 543)

Diameter = Maximum value of leftDepth + rightDepth across all nodes (the longest path does not necessarily pass through the root).

private int globalMaxDiameter = 0;

public int diameterOfBinaryTree(TreeNode root) {
    calculateDepth(root);
    return globalMaxDiameter;
}

// Returns the longest single-sided path starting from node
private int calculateDepth(TreeNode node) {
    if (node == null) return 0;
    
    int left  = calculateDepth(node.left);
    int right = calculateDepth(node.right);
    
    // Update global diameter (sum of left and right branch paths)
    globalMaxDiameter = Math.max(globalMaxDiameter, left + right);
    
    // Return max single branch depth + current node
    return Math.max(left, right) + 1;
}

Note: For edge counting, ans uses left + right (not adding 1 to the sum), but the return increments by 1 because it represents node count from children to parent.

Binary Tree Maximum Path Sum (LeetCode 124)

Paths can start/end anywhere; nodes can have negative values.

private int maxPathVal = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    calculateGain(root);
    return maxPathVal;
}

// Returns the maximum gain from a sub-path extending downward from node
private int calculateGain(TreeNode node) {
    if (node == null) return 0;
    
    // Logic: Treat negative branches as 0 (i.e., ignore them)
    int leftGain  = Math.max(calculateGain(node.left),  0);
    int rightGain = Math.max(calculateGain(node.right), 0);
    
    // Total path sum if this node is the highest point (peak) of the path
    maxPathVal = Math.max(maxPathVal, node.val + leftGain + rightGain);
    
    // Return the value of the node plus only the stronger of the two branches
    return node.val + Math.max(leftGain, rightGain);
}

Diameter vs. Maximum Path Sum

Binary Tree Longest Consecutive Sequence (LeetCode 298)

Parent $\rightarrow$ Child direction, absolute values must be strictly increasing by 1.

private int maxConsecutiveLen = 0;

public int longestConsecutive(TreeNode root) {
    dfs(root, null, 0);
    return maxConsecutiveLen;
}

private void dfs(TreeNode node, TreeNode parent, int currentLen) {
    if (node == null) return;
    
    // If consecutive, increment; otherwise reset to 1
    int length = (parent != null && node.val == parent.val + 1) ? currentLen + 1 : 1;
    maxConsecutiveLen = Math.max(maxConsecutiveLen, length);
    
    dfs(node.left,  node, length);
    dfs(node.right, node, length);
}

Summary Template

Post-order DFS Template (Global Max Update)

int globalResult = InitialValue;

int dfs(node) {
    if (node == null) return BaseValue (0 or -INF);
    
    left  = dfs(node.left);
    right = dfs(node.right);
    
    // 1. Global Update: Consider node as the path peak
    globalResult = max(globalResult, combine(left, right, node.val));
    
    // 2. Local Return: Best single branch to extend upward
    return bestSingleBranch(left, right, node.val);
}

Applicable Problems: Diameter, Maximum Path Sum, Longest Sequential Chain, etc.