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

DP on Trees Maximum Path Sum

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

🎯 Goal: Build a 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 logic to compute the maximum path sum, and finally print the result.

📋 What You'll Learn

Create a tree using a Node class with val, left, and right properties

Create the exact tree structure with nodes having values 1, 2, 3, 4, and 5

Use a variable maxSum to keep track of the maximum path sum found

Write a recursive function maxPathSumHelper that returns the maximum path sum starting from a node

Print the final 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 or resource flows.

💼 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 Nodes

Create a class called Node with a constructor that takes val, left, and right. Then create the exact tree with root node value 1, left child 2, right child 3, left child of 2 as 4, and right child of 2 as 5.

DSA Javascript

// Define the Node class and create the tree nodes
// Your code here

Hint

Define the Node class with val, left, and right. Then build the tree exactly as described.

2

Set Up Maximum Sum Variable

Create a variable called maxSum and set it to Number.NEGATIVE_INFINITY to keep track of the maximum path sum found so far.

DSA Javascript

class Node {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

const root = new Node(1,
    new Node(2,
        new Node(4),
        new Node(5)
    ),
    new Node(3)
);

// Create maxSum variable
// Your code here

Hint

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

3

Write Recursive Function to Find Maximum Path Sum

Write a recursive function called maxPathSumHelper that takes a node. It should return the maximum path sum starting from this node going down. Update maxSum inside the function by considering the sum of the node's value plus the maximum sums from left and right children if they are positive. Use Math.max to ignore negative sums.

DSA Javascript

function maxPathSumHelper(node) {
    if (node === null) return 0;
    const leftMax = Math.max(0, maxPathSumHelper(node.left));
    const rightMax = Math.max(0, maxPathSumHelper(node.right));
    const currentSum = node.val + leftMax + rightMax;
    maxSum = Math.max(maxSum, currentSum);
    return node.val + Math.max(leftMax, rightMax);
// Call the function and print maxSum

Hint

Use recursion to get max sums from left and right. Use Math.max(0, ...) to ignore negative sums. Update maxSum with the sum including both sides.

4

Compute and Print the Maximum Path Sum

Call maxPathSumHelper with root to compute the maximum path sums. Then print the value of maxSum.

DSA Javascript

Hint

Call maxPathSumHelper(root) to start the recursion. Then print maxSum to see the maximum path sum.

Practice

1. What does the "maximum path sum" in a binary tree represent?
Maximum path sum means:

easy

A. The largest sum of node values along any path in the tree

B. The number of nodes in the longest path

C. The smallest sum of node values along any path

D. The sum of all node values in the tree

Solution

1. Step 1: Understand the path definition

   A path in a tree is any sequence of nodes connected by edges, not necessarily starting at the root.

2. Step 2: Define maximum path sum meaning

   The maximum path sum is the highest total value you get by adding node values along any such path.

3. Final Answer:

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

4. Quick Check:

   Maximum path sum = largest node value sum [OK]

Hint: Maximum path sum is about node values, not count or minimum [OK]

Common Mistakes:

• Confusing path length with sum
• Thinking path must start at root
• Choosing sum of all nodes instead of max path

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

function maxPathSum(node) {
  if (___) return 0;
  // rest of code
}

easy

A. node.value === 0

B. node.left === null && node.right === null

C. node === null

D. node === undefined

Solution

1. Step 1: Identify when recursion should stop

   When the node is empty (null), there is no path, so return 0.

2. Step 2: Check options for base case

   Only checking if node is null correctly handles leaf children and empty trees.

3. Final Answer:

   node === null -> Option C

4. Quick Check:

   Base case: node null means no path [OK]

Hint: Base case is node === null to stop recursion [OK]

Common Mistakes:

• Using node.value === 0 which is incorrect
• Checking both children null instead of node null
• Using node === undefined which is less common

3. What is the output of the following code snippet?

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function maxPathSum(root) {
  let maxSum = -Infinity;
  function dfs(node) {
    if (node === null) return 0;
    let left = Math.max(dfs(node.left), 0);
    let right = Math.max(dfs(node.right), 0);
    maxSum = Math.max(maxSum, node.val + left + right);
    return node.val + Math.max(left, right);
  }
  dfs(root);
  return maxSum;
}

const tree = new TreeNode(1, new TreeNode(2), new TreeNode(3));
console.log(maxPathSum(tree));

medium

A. 6

B. 5

C. 3

D. 1

Solution

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

   For leaf nodes 2 and 3, max path sum is their value (2 and 3). For root 1, left=2, right=3, sum=1+2+3=6.

2. Step 2: Update maxSum and return correct values

   maxSum updates to 6 at root. Return values propagate correctly.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Sum of 1+2+3 = 6 [OK]

Hint: Add node + max left + max right, ignore negatives [OK]

Common Mistakes:

• Forgetting to ignore negative sums
• Returning node.val + left + right instead of max(left, right)
• Confusing maxSum update with return value

4. Find the bug in this code for maximum path sum in a binary tree:

function maxPathSum(root) {
  let maxSum = -Infinity;
  function dfs(node) {
    if (!node) return 0;
    let left = dfs(node.left);
    let right = dfs(node.right);
    maxSum = Math.max(maxSum, node.val + left + right);
    return node.val + Math.max(left, right);
  }
  dfs(root);
  return maxSum;
}

medium

A. It returns maxSum before dfs call

B. It does not ignore negative sums from children

C. It uses wrong base case condition

D. It adds node.val twice in maxSum

Solution

1. Step 1: Check handling of negative child sums

   The code uses left = dfs(node.left) directly without ignoring negatives, which can reduce maxSum incorrectly.

2. Step 2: Correct approach to ignore negatives

   Should use left = Math.max(dfs(node.left), 0) and similarly for right to avoid negative paths.

3. Final Answer:

   It does not ignore negative sums from children -> Option B

4. Quick Check:

   Ignore negatives to maximize path sum [OK]

Hint: Use Math.max(childSum, 0) to skip negative paths [OK]

Common Mistakes:

• Not ignoring negative sums
• Returning before dfs call
• Wrong base case check

5. Given a binary tree where nodes can have negative values, how would you modify the maximum path sum algorithm to handle the case where all node values are negative?
Choose the best approach:

hard

A. Initialize maxSum to 0 and ignore negative sums

B. Only consider paths starting at the root

C. Return 0 if all nodes are negative

D. Initialize maxSum to -Infinity and allow paths with negative sums

Solution

1. Step 1: Understand negative values impact

   If all nodes are negative, ignoring negative sums by replacing with 0 would incorrectly return 0 instead of the max negative value.

2. Step 2: Use -Infinity initialization and allow negative sums

   Initialize maxSum to -Infinity and do not ignore negative sums completely, so the max negative node is chosen.

3. Final Answer:

   Initialize maxSum to -Infinity and allow paths with negative sums -> Option D

4. Quick Check:

   Allow negative sums to handle all-negative nodes [OK]

Hint: Use -Infinity start and allow negatives for all-negative trees [OK]

Common Mistakes:

• Ignoring negatives leads to wrong zero result
• Returning 0 when no positive path exists
• Restricting paths to root only