What happens if you not ignoring negative gains from subtrees?

Path sum decreases incorrectly, leading to wrong max sum Fix: Use max(child_gain, 0) to ignore negative contributions

What happens if you returning sum of both children to parent?

Incorrect path sums and double counting, causing wrong results Fix: Return node value plus max of left or right gain only

What happens if you not updating global max path sum at each node?

Misses paths that bend at current node, leading to suboptimal answer Fix: Update global max with node.val + left_gain + right_gain at each node

What happens if you using recursion without base case for null nodes?

Runtime errors or infinite recursion Fix: Return 0 for null nodes in recursion

Interview Prepchallenge-problemshardFacebookAmazonGoogleMicrosoft

Binary Tree Maximum Path Sum

Choose your preparation mode4 modes available

Try It Solution Trace

Start learning this pattern below

Jump into concepts and practice - no test required

Recommended

Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong

🎯

Binary Tree Maximum Path Sum

hardMIXEDFacebookAmazonGoogle

Imagine you are analyzing a network of connected nodes representing a power grid, and you want to find the path that yields the maximum total power output, even if it passes through the central hub and branches out.

💡 This problem involves finding the maximum sum path in a binary tree, which is challenging because the path can start and end at any node, not necessarily the root or leaves. Beginners often struggle to understand how to consider paths that bend at a node and how to efficiently compute the maximum sum without redundant calculations.

📋

Problem Statement

Given a non-empty binary tree, find the maximum path sum. A path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

The number of nodes in the tree is in the range [1, 10^5].-10^4 <= Node.val <= 10^4

💡

Example

Input"[1,2,3]"

Output6

The path with maximum sum is 2 -> 1 -> 3, which sums to 6.

Input"[-10,9,20,null,null,15,7]"

Output42

The path with maximum sum is 15 -> 20 -> 7, which sums to 42.

Single node tree → output is the node's value
All nodes have negative values → output is the maximum single node value
Tree with only left children → path is the sum of all nodes
Tree with only right children → path is the sum of all nodes

⚠️

Common Mistakes

Not ignoring negative gains from subtrees

Path sum decreases incorrectly, leading to wrong max sum

✅ Use max(child_gain, 0) to ignore negative contributions

Returning sum of both children to parent

Incorrect path sums and double counting, causing wrong results

✅ Return node value plus max of left or right gain only

Not updating global max path sum at each node

Misses paths that bend at current node, leading to suboptimal answer

✅ Update global max with node.val + left_gain + right_gain at each node

Using recursion without base case for null nodes

Runtime errors or infinite recursion

✅ Return 0 for null nodes in recursion

Assuming path must start at root or leaf

Incorrect max path sum calculation

✅ Allow path to start and end at any node

🧠

Brute Force (Pure Recursion / Nested Loops / etc.)

💡 Starting with brute force helps understand the problem's complexity by trying all possible paths, even though it's inefficient. It lays the foundation for more optimized solutions.

Intuition

Try every possible path in the tree by exploring all nodes and all paths starting from each node, then find the maximum sum among them.

Algorithm

Define a helper function to compute the maximum path sum starting from a given node.
For each node in the tree, compute the maximum path sum that passes through it by exploring all possible paths.
Keep track of the global maximum path sum found so far.
Return the global maximum after exploring all nodes.

💡 This approach is hard because it redundantly computes path sums multiple times and doesn't reuse results, leading to exponential time.

</>

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxPathSum(root):
    max_sum = float('-inf')

    def max_gain(node):
        nonlocal max_sum
        if not node:
            return 0
        left_gain = max(max_gain(node.left), 0)
        right_gain = max(max_gain(node.right), 0)
        price_newpath = node.val + left_gain + right_gain
        max_sum = max(max_sum, price_newpath)
        return node.val + max(left_gain, right_gain)

    max_gain(root)
    return max_sum

# Driver code
if __name__ == '__main__':
    root = TreeNode(-10)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(maxPathSum(root))  # Output: 42

Line Notes

def maxPathSum(root):Defines the main function to compute max path sum

max_sum = float('-inf')Initialize global max to smallest possible to handle negative values

def max_gain(node):Helper function to compute max gain from current node

if not node:Base case: null nodes contribute 0 to path sum

left_gain = max(max_gain(node.left), 0)Ignore negative gains from left subtree

right_gain = max(max_gain(node.right), 0)Ignore negative gains from right subtree

price_newpath = node.val + left_gain + right_gainSum if path passes through current node including both children

max_sum = max(max_sum, price_newpath)Update global max if current path is better

return node.val + max(left_gain, right_gain)Return max gain to parent, only one side can be extended

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    private int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    private int maxGain(TreeNode node) {
        if (node == null) return 0;
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);
        int priceNewPath = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, priceNewPath);
        return node.val + Math.max(leftGain, rightGain);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(-10);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        Solution sol = new Solution();
        System.out.println(sol.maxPathSum(root)); // Output: 42
    }
}

Line Notes

private int maxSum = Integer.MIN_VALUE;Initialize global max to smallest integer to handle negatives

public int maxPathSum(TreeNode root) {Main function to start recursion

if (node == null) return 0;Base case: null nodes contribute zero

int leftGain = Math.max(maxGain(node.left), 0);Ignore negative left subtree sums

int rightGain = Math.max(maxGain(node.right), 0);Ignore negative right subtree sums

int priceNewPath = node.val + leftGain + rightGain;Sum if path passes through current node

maxSum = Math.max(maxSum, priceNewPath);Update global max if better path found

return node.val + Math.max(leftGain, rightGain);Return max gain to parent, only one side extended

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
    int maxSum = INT_MIN;
public:
    int maxPathSum(TreeNode* root) {
        maxGain(root);
        return maxSum;
    }
private:
    int maxGain(TreeNode* node) {
        if (!node) return 0;
        int leftGain = max(maxGain(node->left), 0);
        int rightGain = max(maxGain(node->right), 0);
        int priceNewPath = node->val + leftGain + rightGain;
        maxSum = max(maxSum, priceNewPath);
        return node->val + max(leftGain, rightGain);
    }
};

int main() {
    TreeNode* root = new TreeNode(-10);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    Solution sol;
    cout << sol.maxPathSum(root) << endl; // Output: 42
    return 0;
}

Line Notes

int maxSum = INT_MIN;Initialize global max to smallest int to handle negative values

int maxPathSum(TreeNode* root) {Main function to start recursion

if (!node) return 0;Base case: null nodes contribute zero

int leftGain = max(maxGain(node->left), 0);Ignore negative left subtree sums

int rightGain = max(maxGain(node->right), 0);Ignore negative right subtree sums

int priceNewPath = node->val + leftGain + rightGain;Sum if path passes through current node

maxSum = max(maxSum, priceNewPath);Update global max if better path found

return node->val + max(leftGain, rightGain);Return max gain to parent, only one side extended

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function maxPathSum(root) {
    let maxSum = -Infinity;

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

    maxGain(root);
    return maxSum;
}

// Driver code
const root = new TreeNode(-10,
    new TreeNode(9),
    new TreeNode(20, new TreeNode(15), new TreeNode(7))
);
console.log(maxPathSum(root)); // Output: 42

Line Notes

let maxSum = -Infinity;Initialize global max to smallest number to handle negatives

function maxGain(node) {Helper function to compute max gain from current node

if (!node) return 0;Base case: null nodes contribute zero

let leftGain = Math.max(maxGain(node.left), 0);Ignore negative left subtree sums

let rightGain = Math.max(maxGain(node.right), 0);Ignore negative right subtree sums

let priceNewPath = node.val + leftGain + rightGain;Sum if path passes through current node

maxSum = Math.max(maxSum, priceNewPath);Update global max if better path found

return node.val + Math.max(leftGain, rightGain);Return max gain to parent, only one side extended

⏱

Complexity

TimeO(n)

SpaceO(h)

Each node is visited once in postorder traversal; recursion stack uses space proportional to tree height h.

💡 For n=100,000 nodes and balanced tree height ~17, this means about 100,000 operations and stack depth 17, which is efficient.

Interview Verdict: Accepted

Though this looks like brute force, this recursive approach is actually optimal for this problem and accepted in interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Recursive with global tracking)	`O(n)`	`O(h)`	Yes (deep recursion)	No (only sum returned)	Code this approach; it is optimal and accepted
2. Iterative Postorder Traversal	`O(n)`	`O(n)`	No	No	Mention if recursion depth is a concern
3. Naive Brute Force (Try all paths)	`O(n^2) or worse`	`O(h)`	Yes	No	Mention only to explain problem complexity

Practice

(1/5)

1. You need to visit all nodes of a binary tree in the order: root node first, then recursively the left subtree, followed by the right subtree. Which algorithmic approach guarantees this traversal order efficiently without extra space for recursion or stack?

easy

A. Postorder traversal using two stacks

B. Level-order traversal using a queue

C. Morris preorder traversal using threaded binary tree

D. Inorder traversal using recursion

3. Examine the following buggy code snippet for summing root-to-leaf numbers using DFS recursion. Which line contains the subtle bug causing incorrect sums on some inputs?

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        self.total = 0
        def dfs(node, current_number):
            if not node:
                return
            current_number = current_number * 10 + node.val
            self.total += current_number  # Bug here
            if not node.left and not node.right:
                return
            dfs(node.left, current_number)
            dfs(node.right, current_number)
        dfs(root, 0)
        return self.total

medium

A. Line with 'if not node:' return statement

B. Line adding current_number to self.total

C. Line checking if node is leaf

D. Line calling dfs on node.right

Start learning this pattern below

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Understand traversal order requirement

Step 2: Identify approach with no extra space

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem constraints

Step 2: Recognize the optimal approach

Final Answer:

Quick Check:

Solution

Step 1: Understand when sums should be added

Step 2: Identify incorrect addition

Final Answer:

Quick Check:

Solution

Step 1: Understand traversal constraints

Step 2: Use parent pointers to simulate traversal

Final Answer:

Quick Check:

Solution

Step 1: Understand problem constraints

Step 2: Evaluate approaches

Step 3: Two-pointer technique

Final Answer:

Quick Check: