Binary Tree Maximum Path Sum

[kokocan12]

Problem

When a root node of binary tree is given, find max-sum of sequence of nodes.
Sequence of nodes means that traverse node to node, but not visit same node.

example
/*
     -100
     /   \
    2     3
   /       \ 
  4         7
*/
Node(7) -> Node(3) is the sequence that has sum of 10.

/*
       1
     /   \
    2     3 
   / \   / \
  4   5 6   7
*/

Node(7) -> Node(3) -> Node(1) -> Node(2) -> Node(5) is the sequence that has sum of 18.

Naive Approach

We can get a single maximum sum path, that start from parent to child.

We can also divide this problem to [LEFT-SIDE] + head + [RIGHT-SIDE].
Then, repeat this at every node.

The code is below.

const maxPathSum = function(root) {
    
    let maxSum = Number.NEGATIVE_INFINITY;
    
    function pathSum(root, sum, tempMax = [Number.NEGATIVE_INFINITY]) {
        if(root === null) return tempMax[0];
        
        sum = sum + root.val
        
        tempMax[0] = Math.max(tempMax[0], sum);
        
        pathSum(root.left, sum, tempMax);
        pathSum(root.right, sum, tempMax);
        
        
        return tempMax[0];
    }
    
    function travel(root) {
        if(root === null) return;
        
        const temp = root.val + Math.max(pathSum(root.left, 0), 0) + Math.max(pathSum(root.right, 0), 0);
        
        maxSum = Math.max(temp, maxSum);
        
        travel(root.left);
        travel(root.right);
    }
    
    travel(root);
    
    
    return maxSum;
};

Better Way

The algorithm above has a time complexity of O(n^2), because it visits same node many times.
We can reduce time complexity to O(n) by combining travel and pathSum into one.

The node has two values, one is max path part(the connection part), it will be used as a child node.
The other one is complete part, where the node is the head of the connection.

The code is below.

const maxPathSum = function(root) {
    
    let maxSum = Number.NEGATIVE_INFINITY;
    
    function pathSum(node) {
        if(node === null) return 0;
        
        const val = node.val;
        
        let left = pathSum(node.left);
        let right = pathSum(node.right);
        left = Math.max(left, 0);
        right = Math.max(right, 0);
        
        // It is the complete part.
        maxSum = Math.max((val + left + right), maxSum);
        
        // It is the connection part.
        return val + Math.max(left, right);
    }
    
    pathSum(root);
    
    return maxSum;
};