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 from each fork and combine them carefully.

      1
     / \
    2   3
   / \
  4   5

Each node has a value. We want the path with the largest sum anywhere in this tree.

Dry Run Walkthrough

Input: Tree with nodes: 1(10), 2(2), 3(10), 4(20), 5(1), edges: 1-2, 1-3, 2-4, 2-5

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

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

Node 4 max single path = 20

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

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

Node 5 max single path = 1

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

Step 3: At node 2, check children 4 and 5: max single paths 20 and 1

Node 2 max single path = max(2 + 20, 2 + 1, 2) = 22

Why: Choose best child path plus node 2's value

Step 4: At node 2, max path through node = 20 + 2 + 1 = 23

Update global max path = 23

Why: Path can go through node 2 connecting both children

Step 5: At node 3 (leaf), max single path = 10

Node 3 max single path = 10

Why: Leaf node value

Step 6: At node 1, check children 2 and 3: max single paths 22 and 10

Node 1 max single path = max(10 + 22, 10 + 10, 10) = 32

Why: Choose best child path plus node 1's value

Step 7: At node 1, max path through node = 22 + 10 + 10 = 42

Update global max path = 42

Why: Path can go through node 1 connecting both children

Result:

Maximum path sum = 42

Annotated Code

DSA C

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

// Tree node structure
typedef struct Node {
    int val;
    struct Node** children;
    int child_count;
} Node;

// Global variable to track max path sum
int max_path_sum = INT_MIN;

// Function to create a new node
Node* newNode(int val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = val;
    node->children = NULL;
    node->child_count = 0;
    return node;
}

// Add child to a node
void addChild(Node* parent, Node* child) {
    parent->child_count++;
    parent->children = (Node**)realloc(parent->children, parent->child_count * sizeof(Node*));
    parent->children[parent->child_count - 1] = child;
}

// DFS function returns max single path sum from this node down
int dfs(Node* node) {
    if (!node) return 0;

    int max1 = 0, max2 = 0; // top two max child paths

    // Check all children
    for (int i = 0; i < node->child_count; i++) {
        int child_sum = dfs(node->children[i]);
        if (child_sum > max1) {
            max2 = max1;
            max1 = child_sum;
        } else if (child_sum > max2) {
            max2 = child_sum;
        }
    }

    // Max single path from this node
    int max_single = node->val + (max1 > 0 ? max1 : 0);

    // Max path through this node (could connect two children)
    int max_top = node->val + (max1 > 0 ? max1 : 0) + (max2 > 0 ? max2 : 0);

    if (max_top > max_path_sum) {
        max_path_sum = max_top;
    }

    return max_single;
}

int main() {
    // Build tree from dry run example
    Node* n1 = newNode(10);
    Node* n2 = newNode(2);
    Node* n3 = newNode(10);
    Node* n4 = newNode(20);
    Node* n5 = newNode(1);

    addChild(n1, n2);
    addChild(n1, n3);
    addChild(n2, n4);
    addChild(n2, n5);

    dfs(n1);

    printf("Maximum path sum = %d\n", max_path_sum);

    // Free memory omitted for brevity
    return 0;
}

for (int i = 0; i < node->child_count; i++) {

Traverse all children to find their max single path sums

int child_sum = dfs(node->children[i]);

Recursively get max single path sum from child

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

Keep track of top two max child paths for possible path through node

int max_single = node->val + (max1 > 0 ? max1 : 0);

Max single path from node includes node value plus best child path if positive

int max_top = node->val + (max1 > 0 ? max1 : 0) + (max2 > 0 ? max2 : 0);

Max path through node can connect two best child paths plus node value

if (max_top > max_path_sum) { max_path_sum = max_top; }

Update global max path sum if current path is better

return max_single;

Return max single path sum for parent's calculation

Output

Maximum path sum = 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 reduces to O(n)

Edge Cases

Single node tree

Returns the node's value as max path sum

DSA C

if (!node) return 0;

All negative values

Max path sum is the largest single node value

DSA C

int max_single = node->val + (max1 > 0 ? max1 : 0);

Tree with zero or no children

Handles leaf nodes correctly by returning their value

DSA C

if (!node) 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 to combine child results efficiently.

Common Mistakes

Mistake: Only considering paths starting at root or leaves, missing paths through internal nodes
Fix: Calculate max path through each node by combining top two child paths

Mistake: Not handling negative child sums properly, causing incorrect max sums
Fix: Ignore negative child sums by taking max with zero before adding

Summary

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

Use when you need the best path sum anywhere in a tree, not just from root or leaves.

The key is to track the top two child paths at each node to consider paths passing through it.

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 along any path between two nodes in the tree

B. The number of nodes in the longest path of the tree

C. The sum of all node values in the tree

D. The height of the tree

Solution

1. Step 1: Understand the problem definition

   The maximum path sum is about finding the path between any two nodes that yields the highest sum of node values.

2. Step 2: Differentiate from other tree properties

   Unlike longest path or height, maximum path sum focuses on the sum of node values, not count or depth.

3. Final Answer:

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

4. Quick Check:

   Maximum path sum = largest node value sum [OK]

Hint: Maximum path sum is about sums, not counts or heights [OK]

Common Mistakes:

• Confusing maximum path sum with longest path length
• Thinking it is the sum of all nodes
• Mixing it up with tree height

2. Which of the following is the correct base case initialization for a recursive function computing maximum path sum in a binary tree node in C?

easy

A. if (node == NULL) return INT_MIN;

B. if (node == NULL) return -1;

C. if (node == NULL) return 1;

D. if (node == NULL) return 0;

Solution

1. Step 1: Understand base case for null nodes

   For maximum path sum, null nodes should contribute 0 to the path sum as they do not add any value.

2. Step 2: Choose appropriate return value

   Returning 0 ensures that null nodes do not affect the sum and allows the recursion to proceed correctly.

3. Final Answer:

   if (node == NULL) return 0; -> Option D

4. Quick Check:

   Base case returns 0 to represent no contribution from null nodes [OK]

Hint: Use 0 for null nodes to avoid affecting sums [OK]

Common Mistakes:

• Returning INT_MIN which can cause incorrect sums
• Returning positive values for null nodes
• Returning 1 or -1 which are arbitrary and incorrect

3. Consider the following C code snippet for maximum path sum in a binary tree node structure. What is the output printed by printf("%d", maxSum); after calling maxPathSum(root); on the tree below?

Tree structure:
1
/ \\
2 3

typedef struct Node {
    int val;
    struct Node* left;
    struct Node* right;
} Node;

int maxSum = INT_MIN;

int maxPathSumUtil(Node* root) {
    if (!root) return 0;
    int left = maxPathSumUtil(root->left);
    int right = maxPathSumUtil(root->right);
    int maxSingle = (left > right ? left : right) + root->val;
    int maxTop = (left + right + root->val);
    if (maxTop > maxSum) maxSum = maxTop;
    return maxSingle > root->val ? maxSingle : root->val;
}

int maxPathSum(Node* root) {
    maxSum = INT_MIN;
    maxPathSumUtil(root);
    return maxSum;
}

medium

A. 3

B. 5

C. 6

D. 4

Solution

1. Step 1: Calculate max path sums for each node

   For node 2 and 3, maxSingle = 2 and 3 respectively, maxTop = 2 and 3. For root 1, left=2, right=3, maxSingle = max(2,3)+1=4, maxTop=2+3+1=6.

2. Step 2: Update maxSum and return final value

   maxSum updates to 6 at root. The function returns maxSum = 6.

3. Final Answer:

   6 -> Option C

4. Quick Check:

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

Hint: Sum path through root and children for max sum [OK]

Common Mistakes:

• Ignoring path through both children
• Returning maxSingle instead of maxSum
• Not updating global maxSum correctly

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

int maxSum = INT_MIN;

int maxPathSumUtil(Node* root) {
    if (!root) return 0;
    int left = maxPathSumUtil(root->left);
    int right = maxPathSumUtil(root->right);
    int maxSingle = (left > right ? left : right) + root->val;
    int maxTop = (left + right + root->val);
    if (maxSingle > maxSum) maxSum = maxSingle;
    if (maxTop > maxSum) maxSum = maxTop;
    return maxSingle;
}

medium

A. It returns maxSingle without comparing it to root->val

B. It updates maxSum with maxSingle before maxTop, missing some max sums

C. It does not handle negative node values correctly

D. It returns maxSingle but should return maxTop

Solution

1. Step 1: Check return value correctness

   maxSingle should be max of (maxSingle, root->val) to handle negative values properly.

2. Step 2: Identify missing max comparison

   Without comparing maxSingle to root->val, the function may return a smaller sum than root's value alone.

3. Final Answer:

   It returns maxSingle without comparing it to root->val -> Option A

4. Quick Check:

   Return value must consider root->val for negatives [OK]

Hint: Always compare maxSingle with root->val before returning [OK]

Common Mistakes:

• Not handling negative values correctly
• Updating maxSum incorrectly
• Returning maxTop instead of maxSingle

5. Given a binary tree where nodes can have negative values, which approach correctly computes the maximum path sum using dynamic programming on trees?

hard

A. Use a recursive function that returns the maximum path sum including the current node and one child, update a global max with sum of node and both children, and handle negative values by comparing with zero

B. Use a recursive function that returns the maximum path sum including the current node and one child, update a global max with sum of node and both children, and handle negative values by comparing with the node's value itself

C. Use a recursive function that returns the sum of all nodes in the subtree, ignoring negative values, and update global max accordingly

D. Use a recursive function that returns the maximum path sum including the current node and both children always, without any comparison for negative values

Solution

1. Step 1: Understand handling of negative values

   Negative values require comparing max sums with the node's own value to avoid reducing sums by adding negative children.

2. Step 2: Correct recursive approach

   Return max path sum including current node and one child or node alone; update global max with sum of node and both children.

3. Final Answer:

   Use a recursive function that returns the maximum path sum including the current node and one child, update a global max with sum of node and both children, and handle negative values by comparing with the node's value itself -> Option B

4. Quick Check:

   Compare with node value to handle negatives correctly [OK]

Hint: Compare sums with node value itself to handle negatives [OK]

Common Mistakes:

• Ignoring negative values in sums
• Always adding both children without max checks
• Ignoring node's own value in comparisons