Maximum Path Sum in Binary Tree in DSA Typescript - Build from Scratch

Maximum Path Sum in Binary Tree

📖 Scenario: You are working on a program that analyzes a binary tree representing a network of roads with values indicating the quality of each road segment. Your goal is to find the path through the network that yields the highest total quality score.

🎯 Goal: Build a TypeScript program that creates a binary tree, sets up a helper variable, implements a function to find the maximum path sum in the tree, and prints the result.

📋 What You'll Learn

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

Initialize the tree with the exact structure and values given

Create a helper variable maxSum to track the maximum path sum

Write a recursive function maxGain that calculates the maximum gain from each node

Use the function to update maxSum with the highest path sum found

Print the final maxSum value

💡 Why This Matters

🌍 Real World

Finding the maximum path sum in a binary tree can help in network optimization, such as finding the best route in a road network or the most profitable path in decision trees.

💼 Career

Understanding tree traversal and recursive algorithms is essential for software engineering roles, especially those involving data structures, algorithms, and system design.

1

Create the Binary Tree Structure

Create a TreeNode class with a constructor that takes a number val and optional left and right nodes. Then create the exact binary tree with root node value 1, left child 2, and right child 3.

DSA Typescript

// Define TreeNode class and create the binary tree
// Your code here

Hint

Define the TreeNode class first, then create root with left and right children.

2

Add a Helper Variable for Maximum Sum

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

DSA Typescript

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

const root = new TreeNode(1, new TreeNode(2), new TreeNode(3));

// Create maxSum variable
// Your code here

Hint

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

3

Implement the Maximum Path Sum Calculation

Write a recursive function called maxGain that takes a TreeNode | null parameter called node. It should return 0 if node is null. Otherwise, calculate the maximum gain from the left and right children by calling maxGain recursively and taking the maximum of 0 and the returned value. Then update maxSum with the maximum of its current value and the sum of node.val, left gain, and right gain. Finally, return node.val plus the maximum of left gain and right gain.

DSA Typescript

function maxGain(node: TreeNode | null): number {
    if (node === null) {
        return 0;
    const leftGain = Math.max(maxGain(node.left), 0);
    const rightGain = Math.max(maxGain(node.right), 0);
    const priceNewPath = node.val + leftGain + rightGain;
    maxSum = Math.max(maxSum, priceNewPath);
    return node.val + Math.max(leftGain, rightGain);
// Call maxGain and print maxSum

Hint

Use recursion to get max gain from left and right, update maxSum, and return the max gain including current node.

4

Calculate and Print the Maximum Path Sum

Call the maxGain function with the root node to start the calculation. Then print the value of maxSum using console.log(maxSum).

DSA Typescript

Hint

Call maxGain(root) to start, then print maxSum with console.log(maxSum).

Practice

1. What does the "Maximum Path Sum in Binary Tree" problem ask you to find?

easy

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

B. The longest path length in the tree

C. The sum of all node values in the tree

D. The minimum value node in the tree

Solution

1. Step 1: Understand the problem goal

   The problem asks for the maximum sum of values along any path in the binary tree, where a path can start and end at any nodes.

2. Step 2: Differentiate from other tree sums

   This is different from longest path or total sum; it focuses on the maximum sum achievable on any path.

3. Final Answer:

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

4. Quick Check:

   Maximum path sum = highest node value sum [OK]

Hint: Focus on sums along paths, not lengths or totals [OK]

Common Mistakes:

• Confusing path sum with longest path length
• Summing all nodes instead of a path
• Looking for minimum instead of maximum

2. Which TypeScript function signature correctly represents a function to find maximum path sum in a binary tree node?

easy

A. function maxPathSum(root: number[]): number

B. function maxPathSum(root: TreeNode | null): number

C. function maxPathSum(root: string): string

D. function maxPathSum(root: TreeNode): void

Solution

1. Step 1: Identify correct parameter type

   The function should accept a binary tree node or null, so TreeNode | null is correct.

2. Step 2: Identify correct return type

   The function returns a number representing the maximum path sum, so return type is number.

3. Final Answer:

   function maxPathSum(root: TreeNode | null): number -> Option B

4. Quick Check:

   Input: TreeNode or null, Output: number [OK]

Hint: Function input is tree node or null, output is number [OK]

Common Mistakes:

• Using array or string instead of TreeNode
• Returning void instead of number
• Not allowing null as input

3. Given the following TypeScript code, what is the output?

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

function maxPathSum(root: TreeNode | null): number {
  let maxSum = -Infinity;
  function helper(node: TreeNode | null): number {
    if (!node) return 0;
    const left = Math.max(helper(node.left), 0);
    const right = Math.max(helper(node.right), 0);
    maxSum = Math.max(maxSum, node.val + left + right);
    return node.val + Math.max(left, right);
  }
  helper(root);
  return maxSum;
}

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

medium

A. 3

B. 5

C. 1

D. 6

Solution

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

   Node 2 and 3 have no children, so max path sums are 2 and 3. For root 1, left=2, right=3, total=1+2+3=6.

2. Step 2: Determine maximum path sum

   Maximum path sum is max of all nodes' sums: max(2,3,6) = 6.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Sum(1+2+3) = 6 [OK]

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

Common Mistakes:

• Ignoring zero floor for negative sums
• Returning sum of only root and one child
• Confusing return value with maxSum variable

4. Identify the bug in this TypeScript function for maximum path sum:

function maxPathSum(root: TreeNode | null): number {
  let maxSum = 0;
  function helper(node: TreeNode | null): number {
    if (!node) return 0;
    const left = helper(node.left);
    const right = helper(node.right);
    maxSum = Math.max(maxSum, node.val + left + right);
    return node.val + Math.max(left, right);
  }
  helper(root);
  return maxSum;
}

medium

A. Returns node.val + min(left, right) instead of max

B. helper function missing base case

C. maxSum initialized to 0 instead of -Infinity

D. Does not call helper on root

Solution

1. Step 1: Check maxSum initialization

   maxSum initialized to 0 can cause wrong result if all node values are negative.

2. Step 2: Correct initialization for negative values

   Initialize maxSum to -Infinity to handle negative node values correctly.

3. Final Answer:

   maxSum initialized to 0 instead of -Infinity -> Option C

4. Quick Check:

   maxSum must start at -Infinity for negative nodes [OK]

Hint: Initialize maxSum to -Infinity to handle negatives [OK]

Common Mistakes:

• Starting maxSum at 0 causes wrong max for negative trees
• Forgetting base case returns 0
• Using min instead of max for return

5. Given a binary tree with nodes: root= -10, left=9, right=20, right.left=15, right.right=7, what is the maximum path sum?

hard

A. 42

B. 35

C. 27

D. 20

Solution

1. Step 1: Calculate max path sums for subtrees

   Right subtree max path: 15 + 20 + 7 = 42. Left subtree max is 9. Root is -10.

2. Step 2: Determine overall max path sum

   Max path sum is max of 42 (right subtree path), 9 (left), and paths including root. The max is 42.

3. Final Answer:

   42 -> Option A

4. Quick Check:

   Sum(15+20+7) = 42 [OK]

Hint: Check all subtree sums including root, pick max [OK]

Common Mistakes:

• Ignoring path through both children and root
• Choosing sum of root and one child only
• Not considering negative root value impact