Binary Tree Maximum Path Sum - Practice Coding Problems

Binary Tree Maximum Path Sum - Problem

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Input & Output

Example 1 — Basic Tree with Positive Values

$ Input: root = [1,2,3]

› Output: 6

💡 Note: The optimal path is 2 → 1 → 3 with sum = 2 + 1 + 3 = 6

Example 2 — Tree with Negative Values

$ Input: root = [-10,9,20,null,null,15,7]

› Output: 42

💡 Note: The optimal path is 15 → 20 → 7 with sum = 15 + 20 + 7 = 42

Example 3 — Single Node

$ Input: root = [-3]

› Output: -3

💡 Note: The tree has only one node, so the maximum path sum is -3

Constraints

The number of nodes in the tree is in the range [1, 3 × 10⁴]
-1000 ≤ Node.val ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with node values (can be negative)

Find All Paths

Consider paths between any two nodes in the tree

Maximum Sum

Return the path with the highest sum

Key Takeaway

🎯 Key Insight: Use DFS to calculate maximum path through each node, tracking the global maximum

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Facebook 12

The key insight is that for each node, the maximum path sum either passes through that node or lies entirely within one of its subtrees. The optimal DFS approach calculates the maximum path at each node by considering left subtree + node + right subtree. Time: O(n), Space: O(h) where h is tree height.

Common Approaches

Approach	Time	Space	Notes
✓ DFS with Global Maximum	O(n)	O(h)	Use DFS to calculate maximum path sum passing through each node
Brute Force - All Paths Enumeration	O(n³)	O(n)	Generate all possible paths and find the maximum sum

DFS with Global Maximum — Algorithm Steps

For each node, calculate max path from node going down
Consider path passing through current node (left + node + right)
Update global maximum
Return max single-sided path for parent

Visualization

Tap to expand

Step-by-Step Walkthrough

Post-order Traversal

Visit children first, then process current node

Calculate Path Sum

For each node: left_max + node.val + right_max

Update Global Max

Track the maximum path sum found so far

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

int maxSum;

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int maxPathHelper(struct TreeNode* node) {
    if (!node) return 0;
    
    int leftMax = max(0, maxPathHelper(node->left));
    int rightMax = max(0, maxPathHelper(node->right));
    
    int currentPathSum = node->val + leftMax + rightMax;
    maxSum = max(maxSum, currentPathSum);
    
    return node->val + max(leftMax, rightMax);
}

int solution(struct TreeNode* root) {
    if (!root) return 0;
    
    maxSum = INT_MIN;
    maxPathHelper(root);
    return maxSum;
}

struct TreeNode* buildTree(char* s) {
    if (!s || strlen(s) < 3) return NULL;
    
    int val = 0;
    sscanf(s, "[%d", &val);
    return createNode(val);
}

int main() {
    char input[1000];
    fgets(input, sizeof(input), stdin);
    input[strcspn(input, "\n")] = 0;
    
    struct TreeNode* root = buildTree(input);
    printf("%d\n", solution(root));
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once during DFS traversal

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals height of tree

✓ Linear Space

68.5K Views

High Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS with Global Maximum — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler