Maximum Path Sum in Binary Tree in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Maximum Path Sum in a binary tree?

It is the largest sum of node values obtained by any path in the tree. The path can start and end at any nodes, but must follow parent-child connections.

beginner

In the Maximum Path Sum problem, must the path go through the root?

No. The path can start and end at any nodes in the tree, not necessarily including the root.

intermediate

Why do we use a helper function that returns the maximum gain from a node in the Maximum Path Sum problem?

Because we want to find the best path sum that can be extended upwards to the parent. The helper returns the maximum sum of a path starting at the current node and going down one side.

intermediate

What does it mean if the maximum gain from a child node is negative in the Maximum Path Sum problem?

We ignore that child's path by taking zero instead, because adding a negative sum would reduce the total path sum.

intermediate

How do we update the global maximum path sum during recursion in the Maximum Path Sum problem?

At each node, we consider the sum of the node's value plus maximum gains from left and right children. If this sum is greater than the current global maximum, we update it.

In the Maximum Path Sum problem, what does the helper function return?

A Maximum path sum including both left and right children

B Sum of all nodes in the tree

C Minimum path sum from root to leaf

D Maximum gain from the current node to one child path

The helper returns the maximum gain from the current node to one child path, which can be extended upwards.

If a child node's maximum gain is negative, what should we do?

A Add it to the path sum

B Ignore it by taking zero

C Subtract it from the path sum

D Stop recursion

Negative gains reduce the path sum, so we ignore them by taking zero.

Can the maximum path sum path pass through the root node?

A Sometimes, if it gives the maximum sum

B Yes, always

C No, never

D Only if the tree is balanced

The path can pass through the root if it yields the maximum sum, but it is not required.

What is the time complexity of the Maximum Path Sum algorithm using recursion?

A O(n)

B O(n log n)

C O(n^2)

D O(log n)

Each node is visited once, so the time complexity is O(n), where n is the number of nodes.

What does the global variable track in the Maximum Path Sum problem?

A Number of nodes visited

B Maximum gain from a single child

C Maximum path sum found so far

D Minimum path sum

The global variable keeps track of the maximum path sum found anywhere in the tree.

Explain how recursion helps find the Maximum Path Sum in a binary tree.

Think about how each node contributes to the path sum and how you combine left and right child results.

Describe the difference between the maximum gain returned by the helper and the global maximum path sum.

One is local to a node's single path, the other is overall best path.

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