Maximum Path Sum in Binary Tree in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Path Sum Calculation

What is the output of the following code that calculates the maximum path sum in a binary tree?

DSA Javascript

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) return 0;
    const left = Math.max(dfs(node.left), 0);
    const 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 root = new TreeNode(-10,
  new TreeNode(9),
  new TreeNode(20, new TreeNode(15), new TreeNode(7))
);
console.log(maxPathSum(root));

A 20

B 35

C 42

D 27

💡 Hint

Think about the path that includes the root's right subtree and its children.

The maximum path sum is 42, coming from the path 15 -> 20 -> 7. The root's value -10 is not included because it lowers the sum. The path 9 alone is smaller. The function correctly calculates the max path sum by considering left and right children and ignoring negative sums.

🧠 Conceptual

intermediate

Understanding Maximum Path Sum Definition

Which of the following best describes the maximum path sum in a binary tree?

A The largest sum of values from any path starting at the root and ending at any leaf.

B The sum of all node values in the tree.

C The largest sum of values from any path that starts at a leaf and ends at the root.

D The largest sum of values from any path between any two nodes in the tree, where the path can start and end at any node.

💡 Hint

The path does not have to start or end at the root or a leaf.

The maximum path sum is the largest sum of values from any path between any two nodes in the tree. The path can start and end at any node and does not have to pass through the root.

❓ Predict Output

advanced

Output of Maximum Path Sum with Negative Values

What is the output of this code that calculates the maximum path sum in a binary tree containing negative values?

DSA Javascript

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) return 0;
    const left = Math.max(dfs(node.left), 0);
    const 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 root = new TreeNode(-3);
console.log(maxPathSum(root));

A 0

B -3

C 3

D null

💡 Hint

Consider that the path can be a single node.

The maximum path sum is -3 because the tree has only one node with value -3. The function returns the maximum sum considering single nodes as paths.

🔧 Debug

advanced

Identify the Error in Maximum Path Sum Implementation

What error will this code produce when calculating the maximum path sum?

DSA Javascript

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) return 0;
    const left = dfs(node.left);
    const right = dfs(node.right);
    maxSum = Math.max(maxSum, node.val + left + right);
    return node.val + Math.max(left, right);
  }
  dfs(root);
  return maxSum;
}

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

A No error, output is 6

B Output is 7, which is incorrect

C Stack overflow error due to infinite recursion

D Output is 4, which is incorrect

💡 Hint

Check if negative values are handled correctly.

The code does not ignore negative sums, but since all values are positive, the output is correct and equals 6 (2 + 1 + 3). No error occurs.

🚀 Application

expert

Maximum Path Sum in a Complex Tree

Given the following binary tree, what is the maximum path sum?

DSA Javascript

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

const root = new TreeNode(10,
  new TreeNode(2,
    new TreeNode(20),
    new TreeNode(1)
  ),
  new TreeNode(10,
    null,
    new TreeNode(-25,
      new TreeNode(3),
      new TreeNode(4)
    )
  )
);

function maxPathSum(root) {
  let maxSum = -Infinity;
  function dfs(node) {
    if (!node) return 0;
    const left = Math.max(dfs(node.left), 0);
    const 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;
}

console.log(maxPathSum(root));

A 42

B 55

C 48

D 60

💡 Hint

Consider the path that includes 20, 2, 10, 10, and ignore negative branches.

The maximum path sum is 42, coming from the path 20 -> 2 -> 10 -> 10, ignoring the negative branch -25. The function correctly calculates this by ignoring negative sums and combining left and right children.