DP on Trees Maximum Path Sum in DSA C - Build from Scratch

DP on Trees Maximum Path Sum

📖 Scenario: You are working on a program that analyzes a tree structure representing a network of connected nodes. Each node has a value, and you want to find the maximum sum of values along any path in the tree. A path can start and end at any nodes but must follow the tree connections.

🎯 Goal: Build a C program that uses dynamic programming on trees to find the maximum path sum. You will create the tree, set up helper variables, write the core logic to compute the maximum path sum, and finally print the result.

📋 What You'll Learn

Create a tree with exactly 5 nodes and specified edges

Use a global variable to track the maximum path sum

Implement a recursive function to compute maximum path sums

Print the maximum path sum after processing the tree

💡 Why This Matters

🌍 Real World

Finding maximum path sums in trees is useful in network analysis, decision trees, and optimizing routes in hierarchical data.

💼 Career

Understanding dynamic programming on trees is important for software engineers working on algorithms, game development, and systems involving hierarchical data.

1

Create the tree structure and nodes

Define a struct called Node with an integer value and an array of pointers to Node called children of size 2. Create 5 nodes named node1 to node5 with values 10, 2, 10, 20, and 1 respectively. Connect the nodes to form this tree:

node1 connected to node2 and node3
node3 connected to node4 and node5

DSA C

# Define struct Node and create 5 nodes with values
# Connect nodes as described

Hint

Use a struct with a fixed size array for children. Initialize each node's value and set children pointers accordingly.

2

Add a global variable to track maximum path sum

Declare a global integer variable called maxSum and initialize it to -1000000 to store the maximum path sum found during traversal.

DSA C

#include 
#include 

typedef struct Node {
    int value;
    struct Node* children[2];
} Node;

Node node1, node2, node3, node4, node5;

int maxSum = -1000000;

int main() {
    node1.value = 10;
    node2.value = 2;
    node3.value = 10;
    node4.value = 20;
    node5.value = 1;

    node1.children[0] = &node2;
    node1.children[1] = &node3;

    node2.children[0] = NULL;
    node2.children[1] = NULL;

    node3.children[0] = &node4;
    node3.children[1] = &node5;

    node4.children[0] = NULL;
    node4.children[1] = NULL;

    node5.children[0] = NULL;
    node5.children[1] = NULL;

    return 0;
}

# Your code here

Hint

Use a global variable outside main to keep track of the maximum sum found.

3

Implement recursive function to find maximum path sum

Write a recursive function called maxPathSum that takes a pointer to Node and returns an integer. It should compute the maximum path sum starting from that node and update the global maxSum if a higher sum is found. Use the children to calculate sums and consider paths through the node and its children.

DSA C

#include 
#include 

typedef struct Node {
    int value;
    struct Node* children[2];
} Node;

Node node1, node2, node3, node4, node5;

int maxSum = -1000000;

int maxPathSum(Node* node) {
    // Your code here
}

int main() {
    node1.value = 10;
    node2.value = 2;
    node3.value = 10;
    node4.value = 20;
    node5.value = 1;

    node1.children[0] = &node2;
    node1.children[1] = &node3;

    node2.children[0] = NULL;
    node2.children[1] = NULL;

    node3.children[0] = &node4;
    node3.children[1] = &node5;

    node4.children[0] = NULL;
    node4.children[1] = NULL;

    node5.children[0] = NULL;
    node5.children[1] = NULL;

    return 0;
}

Hint

Use recursion to get max sums from children. Ignore negative sums by replacing them with zero. Update maxSum if current path sum is higher.

4

Print the maximum path sum

Add a printf statement in main to print the value of maxSum after calling maxPathSum(&node1). The output should be exactly: Maximum Path Sum: 42

DSA C

#include 
#include 

typedef struct Node {
    int value;
    struct Node* children[2];
} Node;

Node node1, node2, node3, node4, node5;

int maxSum = -1000000;

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

int maxPathSum(Node* node) {
    if (node == NULL) {
        return 0;
    }

    int left = maxPathSum(node->children[0]);
    int right = maxPathSum(node->children[1]);

    if (left value + left + right;

    if (currentSum > maxSum) {
        maxSum = currentSum;
    }

    return node->value + max(left, right);
}

int main() {
    node1.value = 10;
    node2.value = 2;
    node3.value = 10;
    node4.value = 20;
    node5.value = 1;

    node1.children[0] = &node2;
    node1.children[1] = &node3;

    node2.children[0] = NULL;
    node2.children[1] = NULL;

    node3.children[0] = &node4;
    node3.children[1] = &node5;

    node4.children[0] = NULL;
    node4.children[1] = NULL;

    node5.children[0] = NULL;
    node5.children[1] = NULL;

    maxPathSum(&node1);

    printf("Maximum Path Sum: %d\n", maxSum);
}

Hint

Print the global maxSum after calling maxPathSum on the root node.

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