Leetcode: Binary Tree Maximum Path Sum | Javascript solution in details

Leetcode
Problem description:

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Solution with javascript

Here is a possible solution to the problem using JavaScript, taking into account that the problem statement allows for non-consecutive nodes in the path:

function maxPathSum(root) {
  let maxSum = Number.MIN_SAFE_INTEGER;

  function dfs(node) {
    if (!node) return 0;
    let left = Math.max(0, dfs(node.left));
    let right = Math.max(0, dfs(node.right));
    maxSum = Math.max(maxSum, left + right + node.val);
    return Math.max(left, right) + node.val;
  }

  dfs(root);

  return maxSum;
}

In this solution, the dfs function returns the maximum path sum that ends at the current node. It calculates this sum by taking the maximum of the left and right sub-paths that originate from the current node, and adding the value of the current node to this maximum. This sum is then used by the parent node to calculate its own path sum.

Additionally, dfs also updates maxSum with the maximum path sum found so far, which includes the current node and both of its sub-paths. This ensures that the maximum path sum is correctly calculated even when the path does not pass through the root node.

Here is a brief description of the steps the code takes:

1. Define a function maxPathSum that takes a root node of a binary tree as its argument. Initialize a variable maxSum with the smallest possible integer value.

2. Define a helper function dfs that takes a node as its argument. This function will be used to traverse the tree and calculate the maximum path sum that ends at the current node.

3. Inside dfs, check if the current node is null. If it is, return 0 from the function.

4. Call dfs recursively on the left and right child nodes of the current node and store the returned values in left and right.

5. Set left and right to 0 if they are negative, using the Math.max function. This ensures that only positive sub-path sums are considered when calculating the maximum path sum for the current node.

6. Update maxSum with the maximum of the current value and the sum of the left sub-path, the right sub-path, and the value of the current node. This calculates the maximum path sum that includes the current node and both of its sub-paths.

7. Return the maximum of the left and right sub-paths plus the value of the current node. This calculates the maximum path sum that ends at the current node and can be used by the parent node to calculate its own path sum.

8. At the end of maxPathSum, call dfs on the root node to start the traversal of the tree and the calculation of the maximum path sum.

9. Return maxSum as the result of maxPathSum.

This solution assumes that the binary tree is represented using node objects with left and right properties that refer to the left and right child nodes, and a val property that holds the value of the node. It also assumes that the tree does not contain any null nodes, i.e., all non-leaf nodes have both

Thanks for reading! share if you find it helpful.