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.