Solving Binary Tree Maximum Path Sum: Finding the Highest Valued Path

The "Binary Tree Maximum Path Sum" problem involves finding a path in a binary tree that produces the highest sum of values. The path may start and end at any node in the tree and can traverse up or down through the tree.

Problem Statement

Given a non-empty binary tree, find the maximum path sum. The path must contain at least one node and does not need to go through the root.

Example

Consider a binary tree:

Input:

root = [1, 2, 3];

Output:

6;

Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Input:

root = [-10, 9, 20, null, null, 15, 7];

Output:

42;

Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Solution Approach - Recursive Depth-First Search

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

function maxPathSum(root: TreeNode | null): number {
  let maxSum = Number.MIN_SAFE_INTEGER;

  function maxGain(node: TreeNode | null): number {
    if (node === null) return 0;

    const leftGain = Math.max(maxGain(node.left), 0);
    const rightGain = Math.max(maxGain(node.right), 0);

    const priceNewPath = node.val + leftGain + rightGain;
    maxSum = Math.max(maxSum, priceNewPath);

    return node.val + Math.max(leftGain, rightGain);
  }

  maxGain(root);
  return maxSum;
}

Breaking Down the Solution

• Recursive Function: The maxGain function calculates the maximum sum starting from each node.
• Path Sum Calculation: At each node, calculate the maximum sum of any path that includes the node.
• Global Maximum: Track the maximum path sum found in the entire tree.

Conclusion

The Binary Tree Maximum Path Sum problem is a complex and intriguing challenge, showcasing the depth and flexibility of recursive algorithms in tree data structures.