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.