Maximum path sum from any node

Time: O(n)

Space: O(h)

Intuition

Path can go through any node, using both subtrees. DFS: at each node, best path = max(0, leftGain) + max(0, rightGain) + node.val. Track global max.

Algorithm

1DFS returns the maximum gain (single path down) from this node.
2At node: leftGain = max(0, dfs(left)). rightGain = max(0, dfs(right)).
3Candidate = leftGain + rightGain + val. Update global max.
4Return val + max(leftGain, rightGain) (can only choose one side for parent path).

Common Pitfalls

•Return val + max(left,right) to parent (can't split the path). Update global max with both sides locally.

Maximum path sum from any node.java

Java

// Approach: DFS. At each node compute max path through it as left+ + right+ + node.val. Track global max.
// Time: O(n) Space: O(h)
class Node {
    int data;
    Node left, right;

    Node(int d) {
        data = d;
        left = right = null;
    }
}

class Solution {
    // Function to return maximum path sum from any node in a tree.
    int findMaxSum(Node node) {
        int maxi[] = new int[1];
        maxi[0] = Integer.MIN_VALUE;
        maxsum(node, maxi);
        return maxi[0];
    }

    public int maxsum(Node node, int maxi[]) {
        if (node == null)
            return 0;
        int leftsum = Math.max(maxsum(node.left, maxi), 0);
        int rightsum = Math.max(maxsum(node.right, maxi), 0);

        maxi[0] = Math.max(maxi[0], leftsum + rightsum + node.data);

        return node.data + Math.max(leftsum, rightsum);
    }
}

Was this solution helpful?