LeetCode 124 – Binary Tree Maximum Path Sum: Problem Description, Analysis, and Java Solution

Problem Description

A path is any sequence of nodes connected by parent‑child links in a binary tree, where each node appears at most once; the path may start and end at any nodes and does not need to pass through the root. The path sum is the sum of node values along the path. Given the root of a binary tree, return the maximum possible path sum.

Problem Analysis

The key constraint is that a node can appear only once in a path, which means that when a node is chosen, at most one of its two children can be selected for the continuation of that particular path. By processing the tree from leaves upward, we can compute for each node the best sum when the node is included and only one child is taken, as well as the best overall sum when both children are taken (if they are positive).

Initial DFS Helper (single‑child selection)

private int dfs(TreeNode root) {
    if (root == null) return 0;
    int left = dfs(root.left);   // max path sum from left child
    int right = dfs(root.right); // max path sum from right child
    // Choose at most one child (or none) and add current node value
    return Math.max(0, Math.max(left, right)) + root.val;
}

This helper mirrors the maximum subarray problem but operates on a binary tree.

Full Solution (allowing both children)

int max = Integer.MIN_VALUE; // global maximum path sum

public int maxPathSum(TreeNode root) {
    dfs(root);
    return max;
}

private int dfs(TreeNode root) {
    if (root == null) return 0;
    int left = dfs(root.left);
    int right = dfs(root.right);
    // If child contributions are positive, include them
    int curMax = Math.max(0, left) + Math.max(0, right) + root.val;
    max = Math.max(max, curMax);
    // Return the best sum for a path that continues upward through the parent
    return Math.max(0, Math.max(left, right)) + root.val;
}

The algorithm records the maximum sum of any path that passes through each node (potentially using both children) and updates a global variable. It then returns the best sum for paths that can be extended to the node's parent.