DP on Trees Maximum Path Sum in DSA C++

Mental Model

We find the biggest sum of values along any path in a tree by checking each node's best paths through its children.

Analogy: Imagine climbing a mountain with many branches. To find the highest path, you check the best routes up each branch and combine them at junctions.

      1
     / \
    2   3
   / \   \
  4   5   6

Dry Run Walkthrough

Input: Tree with nodes and values: 1(10), 2(2), 3(10), 4(20), 5(1), 6(-25), 7(3), 8(4) connected as: 1-2,1-3,2-4,2-5,3-6,6-7,6-8

Goal: Find the maximum sum of values along any path in the tree

Step 1: Start DFS at node 4 (leaf), max path through 4 is 20

Node4: max_single=20, max_top=20

Why: Leaf nodes have max path equal to their own value

Step 2: At node 5 (leaf), max path through 5 is 1

Node5: max_single=1, max_top=1

Why: Leaf nodes have max path equal to their own value

Step 3: At node 2, calculate max_single as max(2 + max_single(4), 2 + max_single(5), 2) = max(22,3,2) = 22; max_top = max(max_top(4), max_top(5), max_single(4)+2+max_single(5), max_single(2)) = max(20,1,20+2+1,22) = 23

Node2: max_single=22, max_top=23

Why: Node 2 combines best child paths and itself

Step 4: At node 7 (leaf), max path through 7 is 3

Node7: max_single=3, max_top=3

Why: Leaf nodes have max path equal to their own value

Step 5: At node 8 (leaf), max path through 8 is 4

Node8: max_single=4, max_top=4

Why: Leaf nodes have max path equal to their own value

Step 6: At node 6, max_single = max(-25 + max_single(7), -25 + max_single(8), -25) = max(-22, -21, -25) = -21; max_top = max(max_top(7), max_top(8), max_single(7)+(-25)+max_single(8), max_single(6)) = max(3,4,3-25+4,-21) = 4

Node6: max_single=-21, max_top=4

Why: Node 6 combines child paths but negative value reduces max_single

Step 7: At node 3, max_single = max(10 + max_single(6), 10) = max(10 - 21, 10) = 10; max_top = max(max_top(6), max_single(3)) = max(4,10) = 10

Node3: max_single=10, max_top=10

Why: Node 3 chooses best path including or excluding child 6

Step 8: At node 1 (root), max_single = max(10 + max_single(2), 10 + max_single(3), 10) = max(10 + 22, 10 + 10, 10) = 32; max_top = max(max_top(2), max_top(3), max_single(2) + 10 + max_single(3), max_single(1)) = max(23, 10, 22 + 10 + 10, 32) = 42

Node1: max_single=32, max_top=42

Why: Root combines best paths from both children plus itself for max path

Result:

Maximum path sum is 42

Annotated Code

DSA C++

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

struct TreeNode {
    int val;
    vector<TreeNode*> children;
    TreeNode(int x) : val(x) {}
};

class Solution {
public:
    int maxSum = INT_MIN;

    int dfs(TreeNode* node) {
        if (!node) return 0;
        int max1 = 0, max2 = 0; // top two max child sums
        for (auto child : node->children) {
            int childSum = dfs(child);
            if (childSum > max1) {
                max2 = max1;
                max1 = childSum;
            } else if (childSum > max2) {
                max2 = childSum;
            }
        }
        int maxSingle = max(node->val, node->val + max1);
        int maxTop = max(maxSingle, node->val + max1 + max2);
        maxSum = max(maxSum, maxTop);
        return maxSingle;
    }

    int maxPathSum(TreeNode* root) {
        dfs(root);
        return maxSum;
    }
};

int main() {
    TreeNode* root = new TreeNode(10);
    TreeNode* n2 = new TreeNode(2);
    TreeNode* n3 = new TreeNode(10);
    TreeNode* n4 = new TreeNode(20);
    TreeNode* n5 = new TreeNode(1);
    TreeNode* n6 = new TreeNode(-25);
    TreeNode* n7 = new TreeNode(3);
    TreeNode* n8 = new TreeNode(4);

    root->children.push_back(n2);
    root->children.push_back(n3);
    n2->children.push_back(n4);
    n2->children.push_back(n5);
    n3->children.push_back(n6);
    n6->children.push_back(n7);
    n6->children.push_back(n8);

    Solution sol;
    cout << sol.maxPathSum(root) << "\n";
    return 0;
}

for (auto child : node->children) { int childSum = dfs(child); ... }

recursively find max path sums from children

if (childSum > max1) { max2 = max1; max1 = childSum; } else if (childSum > max2) { max2 = childSum; }

track top two maximum child sums for combining paths

int maxSingle = max(node->val, node->val + max1);

max path sum including current node and one child

int maxTop = max(maxSingle, node->val + max1 + max2);

max path sum through current node combining two children

maxSum = max(maxSum, maxTop);

update global max path sum

return maxSingle;

return max path sum for parent to use

Output

42

Complexity Analysis

Time: O(n) because we visit each node once in DFS

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Naive approach checking all paths is O(n^2) or worse; DP on trees is efficient

Edge Cases

Single node tree

Returns the node's value as max path sum

DSA C++

if (!node) return 0;

All negative values

Returns the maximum single node value as max path sum

DSA C++

int maxSingle = max(node->val, node->val + max1);

Tree with only one child per node (chain)

Works like max subarray sum along the chain

DSA C++

for (auto child : node->children) { ... }

When to Use This Pattern

When asked for the maximum sum path in a tree, especially if paths can start and end anywhere, use DP on trees to combine child results efficiently.

Common Mistakes

Mistake: Only considering paths from root to leaf, missing paths that go through a node combining two children
Fix: Track top two child sums and consider paths passing through the current node combining both

Mistake: Not handling negative values properly, leading to incorrect sums
Fix: Use max with node value alone to avoid decreasing sums

Summary

Finds the maximum sum of values along any path in a tree using dynamic programming.

Use when you need the highest sum path that can start and end at any nodes in a tree.

The key is to combine the best one-child paths and two-child paths at each node to find the global maximum.

Practice

1. What does the "Maximum Path Sum" in a tree represent in the context of dynamic programming on trees?

easy

A. The largest sum of node values on any path between two nodes in the tree

B. The sum of all node values in the tree

C. The maximum value of a single node in the tree

D. The longest path length in the tree

Solution

1. Step 1: Understand the problem definition

   The maximum path sum is the highest sum of values collected by traveling along any path between two nodes in the tree, not necessarily passing through the root.

2. Step 2: Differentiate from other sums

   It is not the sum of all nodes or just the maximum node value, but the maximum sum along any connected path.

3. Final Answer:

   The largest sum of node values on any path between two nodes in the tree -> Option A

4. Quick Check:

   Maximum path sum = largest sum on any node-to-node path [OK]

Hint: Maximum path sum is about any path, not whole tree sum [OK]

Common Mistakes:

• Confusing maximum path sum with total sum of all nodes
• Thinking it is the maximum single node value
• Assuming path must start at root

2. Which of the following C++ function signatures is correct for a recursive function that computes the maximum path sum in a binary tree node structure defined as struct TreeNode { int val; TreeNode* left; TreeNode* right; };?

easy

A. int maxPathSum(TreeNode root);

B. void maxPathSum(TreeNode root);

C. int maxPathSum(TreeNode* root);

D. int maxPathSum(TreeNode* root, int sum);

Solution

1. Step 1: Check parameter passing

   The tree nodes should be passed as pointers to avoid copying the entire subtree, so TreeNode* is correct.

2. Step 2: Check return type and parameters

   The function returns an integer representing the maximum path sum, so int return type is correct. Additional parameters like int sum are not necessary for the main function signature.

3. Final Answer:

   int maxPathSum(TreeNode* root); -> Option C

4. Quick Check:

   Use pointer parameter and int return type [OK]

Hint: Use pointer parameter and int return type for tree recursion [OK]

Common Mistakes:

• Passing TreeNode by value causing copies
• Using void return type when int is needed
• Adding unnecessary parameters in main signature

3. Consider the following C++ code snippet for maximum path sum in a binary tree:

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

int maxSum = INT_MIN;

int dfs(TreeNode* node) {
  if (!node) return 0;
  int left = max(0, dfs(node->left));
  int right = max(0, dfs(node->right));
  maxSum = max(maxSum, node->val + left + right);
  return node->val + max(left, right);
}

int maxPathSum(TreeNode* root) {
  dfs(root);
  return maxSum;
}

// Tree structure:
//       1
//      / \
//     2   3
//
// What is the output of maxPathSum(root)?

medium

A. 5

B. 6

C. 3

D. 1

Solution

1. Step 1: Calculate dfs values for each node

   For leaf nodes 2 and 3, dfs returns their values (2 and 3). For root 1, left=2, right=3, so maxSum = max(INT_MIN, 1+2+3) = 6.

2. Step 2: Return maxSum after dfs completes

   The function returns maxSum = 6, which is the maximum path sum (2 -> 1 -> 3).

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Max path sum = 2 + 1 + 3 = 6 [OK]

Hint: Add node value plus max left and right sums, ignore negatives [OK]

Common Mistakes:

• Ignoring max(0, dfs(...)) causing negative sums
• Returning node->val + left + right instead of max path
• Confusing maxSum update with return value

4. The following code attempts to compute the maximum path sum in a binary tree but has a bug:

int maxSum = INT_MIN;

int dfs(TreeNode* node) {
  if (!node) return 0;
  int left = dfs(node->left);
  int right = dfs(node->right);
  maxSum = max(maxSum, node->val + left + right);
  return node->val + max(left, right);
}

What is the main issue causing incorrect results?

medium

A. It does not handle null nodes properly

B. It returns the sum of both children instead of max

C. It does not update maxSum correctly

D. It does not ignore negative sums from children

Solution

1. Step 1: Analyze child sums usage

   The code uses raw dfs values for left and right without ignoring negative sums, which can reduce the path sum.

2. Step 2: Identify fix for negative sums

   To fix, use max(0, dfs(...)) to ignore negative sums from children, ensuring path sum only increases or stays same.

3. Final Answer:

   It does not ignore negative sums from children -> Option D

4. Quick Check:

   Use max(0, dfs(child)) to avoid negative sums [OK]

Hint: Always ignore negative child sums with max(0, dfs(child)) [OK]

Common Mistakes:

• Not using max(0, ...) causing negative path sums
• Returning sum of both children instead of max for recursion
• Incorrect maxSum update logic

5. Given a binary tree where nodes can have negative values, how would you modify the standard maximum path sum algorithm to correctly handle the case where the maximum path sum is a single node with a negative value? Choose the best approach.

hard

A. Initialize maxSum with INT_MIN and use max(0, dfs(child)) in recursion

B. Initialize maxSum with 0 and ignore negative node values completely

C. Initialize maxSum with INT_MIN and allow dfs to return negative values without max(0, ...)

D. Initialize maxSum with 0 and always add node values regardless of sign

Solution

1. Step 1: Recall the standard algorithm

   The standard algorithm initializes maxSum to INT_MIN and uses left = max(0, dfs(left)), right = max(0, dfs(right)), updating maxSum = max(maxSum, node.val + left + right). This captures single negative nodes as node.val + 0 + 0.

2. Step 2: Why it handles negatives

   max(0, dfs(child)) prevents extending to negative subtrees but allows dfs to return node.val + 0 (negative if node negative). INT_MIN init captures negative maxima.

3. Step 3: Why A fails

   Without max(0, ...), negative child sums pollute parent updates (e.g., root=-2, left=-3: maxSum wrongly stays -3 instead of -2).

4. Final Answer:

   Initialize maxSum with INT_MIN and use max(0, dfs(child)) in recursion -> Option A

5. Quick Check:

   max(0, dfs(child)) + INT_MIN handles negative single nodes [OK]

Hint: Standard max(0, dfs(child)) + INT_MIN handles negative nodes correctly [OK]

Common Mistakes:

• Omitting max(0, ...) letting negative children reduce parent path sums
• Initializing maxSum with 0 missing negative maxima
• Ignoring all negative nodes