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 and combining them carefully.

Analogy: Imagine climbing a mountain with many branches. To find the highest path, you check the best routes up from each fork and combine them to get the highest total height.

      1
     / \
    2   3
   / \   \
  4   5   6

Dry Run Walkthrough

Input: Tree: 1 / \ 2 3 / \ \ 4 5 6 Values: 1=10, 2=2, 3=10, 4=20, 5=1, 6=-25

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

Step 1: Start at leaf node 4, max path sum from 4 is 20

Node 4: max_single_path=20, max_top=20

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

Step 2: At leaf node 5, max path sum from 5 is 1

Node 5: max_single_path=1, max_top=1

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

Step 3: At node 2, calculate max path sums using children 4 and 5

Node 2: max_single_path = max(2, 2+20, 2+1) = 22
max_top = max(20, 1, 22, 2+20+1=23) = 23

Why: We consider paths through left child, right child, or both plus current node

Step 4: At leaf node 6, max path sum from 6 is -25

Node 6: max_single_path=-25, max_top=-25

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

Step 5: At node 3, calculate max path sums using child 6

Node 3: max_single_path = max(10, 10 + (-25)) = 10
max_top = max(10, -25, 10) = 10

Why: Negative child path is ignored if it reduces sum

Step 6: At root node 1, calculate max path sums using children 2 and 3

Node 1: max_single_path = max(10, 10 + 22, 10 + 10) = 32
max_top = max(23, 10, 32, 22 + 10 + 10 = 42) = 42

Why: Combine best paths from both children plus current node for max path

Result:

Maximum path sum = 42
Path example: 4 -> 2 -> 1 -> 3

Annotated Code

DSA C#

using System;

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

class Solution {
    private int maxSum = int.MinValue;

    public int MaxPathSum(TreeNode root) {
        MaxGain(root);
        return maxSum;
    }

    private int MaxGain(TreeNode node) {
        if (node == null) return 0;

        // max sum on the left subtree
        int leftGain = Math.Max(MaxGain(node.left), 0);
        // max sum on the right subtree
        int rightGain = Math.Max(MaxGain(node.right), 0);

        // price to start a new path where `node` is the highest node
        int priceNewPath = node.val + leftGain + rightGain;

        // update maxSum if priceNewPath is better
        maxSum = Math.Max(maxSum, priceNewPath);

        // for recursion : return the max gain if continue the same path
        return node.val + Math.Max(leftGain, rightGain);
    }
}

class Program {
    static void Main() {
        TreeNode root = new TreeNode(10,
            new TreeNode(2,
                new TreeNode(20),
                new TreeNode(1)),
            new TreeNode(10,
                null,
                new TreeNode(-25,
                    new TreeNode(3),
                    new TreeNode(4))));

        Solution sol = new Solution();
        int result = sol.MaxPathSum(root);
        Console.WriteLine(result);
    }
}

if (node == null) return 0;

stop recursion at null nodes

int leftGain = Math.Max(MaxGain(node.left), 0);

calculate max gain from left child, ignore negative sums

int rightGain = Math.Max(MaxGain(node.right), 0);

calculate max gain from right child, ignore negative sums

int priceNewPath = node.val + leftGain + rightGain;

sum if path passes through current node including both children

maxSum = Math.Max(maxSum, priceNewPath);

update global max path sum if current path is better

return node.val + Math.Max(leftGain, rightGain);

return max gain continuing from current node to one child

Output

42

Complexity Analysis

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

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

vs Alternative: Naive approach checking all paths would be O(n^2) or worse; DP on trees reduces it to linear time

Edge Cases

Tree with all negative values

The algorithm returns the single largest node value as max path sum

DSA C#

int leftGain = Math.Max(MaxGain(node.left), 0);

Tree with single node

Returns the value of the single node

DSA C#

if (node == null) return 0;

Tree with null root

Returns int.MinValue or handles gracefully by returning 0 or minimal sum

DSA C#

if (node == null) return 0;

When to Use This Pattern

When asked to find the maximum sum path in a tree that can start and end anywhere, use DP on trees by computing max gains from children and combining them at each node.

Common Mistakes

Mistake: Not ignoring negative child path sums, which lowers the total path sum
Fix: Use Math.Max(childGain, 0) to ignore negative sums

Mistake: Returning sum of both children plus node without considering continuing path for recursion
Fix: Return node.val + max(leftGain, rightGain) to continue path correctly

Summary

Finds the maximum sum of values along any path in a binary tree.

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

The key is to compute max gains from children ignoring negatives and combine them at each node.

Practice

1. What does the "maximum path sum" in a tree represent in the context of DP on Trees Maximum Path Sum?

easy

A. The sum of all node values in the tree

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

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

D. The longest path length in terms of number of edges

Solution

1. Step 1: Understand the problem definition

   The maximum path sum means the highest total sum of node values collected along any path connecting 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 single node value, but the sum along a path that can include multiple nodes.

3. Final Answer:

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

4. Quick Check:

   Maximum path sum = largest node value sum on any path [OK]

Hint: Maximum path sum is about sums along paths, not single nodes [OK]

Common Mistakes:

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

2. Which of the following C# method signatures is correct for a recursive function that returns the maximum path sum starting from a given tree node?

easy

A. int MaxPathSum(TreeNode node)

B. void MaxPathSum(TreeNode node)

C. int MaxPathSum(int node)

D. TreeNode MaxPathSum(TreeNode node)

Solution

1. Step 1: Identify the return type needed

   The function should return an integer representing the maximum path sum starting from the given node.

2. Step 2: Check parameter type

   The parameter must be a TreeNode object to access node values and children.

3. Final Answer:

   int MaxPathSum(TreeNode node) -> Option A

4. Quick Check:

   Return type int and parameter TreeNode required [OK]

Hint: Return int for sums, input parameter must be TreeNode [OK]

Common Mistakes:

• Using void return type when int is needed
• Passing int instead of TreeNode as parameter
• Returning TreeNode instead of int

3. Consider the following C# code snippet for a binary tree node class and a method to find maximum path sum:

public class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int x) { val = x; }
}

int maxSum = int.MinValue;

int MaxPathSum(TreeNode node) {
    if (node == null) return 0;
    int left = Math.Max(0, MaxPathSum(node.left));
    int right = Math.Max(0, MaxPathSum(node.right));
    maxSum = Math.Max(maxSum, left + right + node.val);
    return Math.Max(left, right) + node.val;
}

// Tree structure:
//       1
//      / \
//     2   3

TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
MaxPathSum(root);
Console.WriteLine(maxSum);

What is the output printed?

medium

A. 1

B. 5

C. 3

D. 6

Solution

1. Step 1: Calculate max path sums for children

   For node 2 and 3, left and right children are null, so returns 0. Max path sum at node 2 and 3 is their own value (2 and 3).

2. Step 2: Calculate max path sum at root

   At root (1), left = max(0, 2) = 2, right = max(0, 3) = 3. maxSum updated to max(-∞, 2+3+1) = 6. Return max(2,3)+1=4.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Sum of path 2->1->3 = 6 [OK]

Hint: Add left + right + node.val for max path at each node [OK]

Common Mistakes:

• Ignoring max(0, child) and using negative sums
• Returning sum without updating maxSum
• Confusing return value with maxSum

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

int maxSum = int.MinValue;

int MaxPathSum(TreeNode node) {
    if (node == null) return 0;
    int left = MaxPathSum(node.left);
    int right = MaxPathSum(node.right);
    maxSum = Math.Max(maxSum, left + right + node.val);
    return Math.Max(left, right) + node.val;
}

What is the bug in this code?

medium

A. It does not ignore negative sums from children

B. It returns the wrong value type

C. It does not update maxSum correctly

D. It does not handle null nodes

Solution

1. Step 1: Analyze child sums usage

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

2. Step 2: Identify fix for negative sums

   We must use Math.Max(0, left) and Math.Max(0, right) to ignore negative sums from children.

3. Final Answer:

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

4. Quick Check:

   Negative child sums must be ignored [OK]

Hint: Use Math.Max(0, childSum) to ignore negatives [OK]

Common Mistakes:

• Not using Math.Max(0, child) causing wrong sums
• Assuming return type is wrong
• Missing null checks (which are present)

5. Given a binary tree where some nodes have negative values, which approach correctly computes the maximum path sum using DP on trees? A) At each node, compute max path sum including both children and update global max; return max path sum including one child plus node value. B) At each node, sum all child node values and return total sum. C) At each node, return the maximum child value only. D) At each node, ignore children and consider only node value.

hard

A. Return the maximum child value only

B. Sum all child node values and return total sum

C. Compute max path sum including both children and update global max; return max path sum including one child plus node value

D. Ignore children and consider only node value

Solution

1. Step 1: Understand the correct DP approach

   The correct approach is to consider the maximum path sum including both children and update a global max, returning the max path sum including one child plus node value.

2. Step 2: Identify the incorrect options

   The other options do not correctly handle the problem. They either sum all children, return only the maximum child value, or ignore children and consider only node value.

3. Final Answer:

   Compute max path sum including both children and update global max; return max path sum including one child plus node value -> Option C

4. Quick Check:

   Correct DP uses both children sums and global max update [OK]

Hint: Include both children sums and update global max [OK]

Common Mistakes:

• Ignoring children nodes in calculation
• Summing all children without max checks
• Returning only child values without node