Maximum path sum

JavaView on GFG

Time: O(n)

Space: O(h)

Problem Overview

Find maximum path sum in binary tree.

See our study guide for structured GFG and LeetCode practice.

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?