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

DP on Trees Maximum Path Sum

📖 Scenario: You are working with a tree data structure representing a network of connected nodes. Each node has a value that can be positive or negative. 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 without revisiting nodes.

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

📋 What You'll Learn

Create a tree using a Node class with value and children properties

Use a helper variable to track the maximum path sum found so far

Implement a recursive function to compute maximum path sums using dynamic programming

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 hierarchical data processing where you want to find the most valuable route or connection.

💼 Career

This problem teaches recursion, dynamic programming on trees, and handling complex data structures, which are common in software engineering interviews and real-world algorithmic challenges.

1

Create the tree nodes and structure

Create a class called Node with a constructor that takes a value (number) and initializes a children array. Then create the following nodes with these exact values: root with value 10, nodeA with value 2, nodeB with value 10, nodeC with value 20, nodeD with value 1, and nodeE with value -25. Connect the nodes to form this tree structure: root has children nodeA and nodeB; nodeB has children nodeC and nodeD; nodeD has child nodeE.

DSA Typescript

class Node {
  value: number;
  children: Node[];
  constructor(value: number) {
    this.value = value;
    this.children = [];
  }
}

// Create nodes and connect them
// Your code here

Hint

Define the Node class first. Then create each node with the exact values. Finally, connect children using the children.push() method.

2

Add a helper variable to track maximum path sum

Create a variable called maxSum and initialize it to Number.NEGATIVE_INFINITY. This will keep track of the highest path sum found during recursion.

DSA Typescript

class Node {
  value: number;
  children: Node[];
  constructor(value: number) {
    this.value = value;
    this.children = [];
  }
}

const root = new Node(10);
const nodeA = new Node(2);
const nodeB = new Node(10);
const nodeC = new Node(20);
const nodeD = new Node(1);
const nodeE = new Node(-25);

root.children.push(nodeA, nodeB);
nodeB.children.push(nodeC, nodeD);
nodeD.children.push(nodeE);

// Create maxSum variable
// Your code here

Hint

Use let maxSum = Number.NEGATIVE_INFINITY to start with the smallest possible number.

3

Implement recursive function to find maximum path sum

Write a function called maxPathSumHelper that takes a node of type Node and returns a number. Inside, recursively compute the maximum path sum for each child. Use these steps: 1) For each child, call maxPathSumHelper(child) and store the results in an array. 2) Find the top two maximum values from these results or use 0 if none are positive. 3) Calculate the current maximum path sum as node.value + max1 + max2. 4) Update maxSum if this current sum is greater. 5) Return node.value + max1 as the maximum sum path starting from this node going down one branch.

DSA Typescript

function maxPathSumHelper(node: Node): number {
  if (!node) return 0;
  const childSums = node.children.map(child => maxPathSumHelper(child));
  const positiveSums = childSums.filter(sum => sum > 0);
  positiveSums.sort((a, b) => b - a);
  const max1 = positiveSums[0] || 0;
  const max2 = positiveSums[1] || 0;
  const currentSum = node.value + max1 + max2;
  if (currentSum > maxSum) {
    maxSum = currentSum;
  return node.value + max1;
// Call function and print maxSum

Hint

Use recursion to get sums from children. Sort to find top two positive sums. Update maxSum if current path sum is bigger. Return the max sum path starting from this node.

4

Print the maximum path sum result

Call maxPathSumHelper(root) to process the tree. Then print the value of maxSum using console.log(maxSum).

DSA Typescript

Hint

Call the helper function with root and then print maxSum to see the maximum path sum.