Maximum path sum

JavaView on GFG

Time: O(n)

Space: O(h)

Intuition

Find maximum path sum in binary tree. Path can start and end at any node.

Algorithm

1Post-order DFS. For each node: left gain = max(0, dfs(left)), right gain = max(0, dfs(right)). Update global max with node+left+right. Return node + max(left, right).

Common Pitfalls

•Same as LC 124. Track global max separately. Return only the best single path for parent use.

Maximum path sum.java

Java

// Approach: DFS postorder. For paths from root to leaf sum values. Track and return maximum path sum.
// Time: O(n) Space: O(h)
class Node {
    int data;
    Node left, right;

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

class Solution {
    int max = Integer.MIN_VALUE;

    int findMaxSum(Node root) {
        f(root);
        return max;
    }

    int f(Node root) {
        if (root == null)
            return 0;
        int left = f(root.left);
        int right = f(root.right);

        max = Math.max(max,
                Math.max(root.data + left + right, Math.max(root.data + left, Math.max(root.data, root.data + right))));
        return root.data + Math.max(Math.max(left, right), 0);
    }
}

Was this solution helpful?