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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Path Sum Calculation

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

DSA Go

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

var maxSum int

func maxPathSum(root *TreeNode) int {
    maxSum = -1 << 31
    maxGain(root)
    return maxSum
}

func maxGain(node *TreeNode) int {
    if node == nil {
        return 0
    }
    leftGain := max(maxGain(node.Left), 0)
    rightGain := max(maxGain(node.Right), 0)
    priceNewPath := node.Val + leftGain + rightGain
    if priceNewPath > maxSum {
        maxSum = priceNewPath
    }
    return node.Val + max(leftGain, rightGain)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    root := &TreeNode{Val: -10}
    root.Left = &TreeNode{Val: 9}
    root.Right = &TreeNode{Val: 20}
    root.Right.Left = &TreeNode{Val: 15}
    root.Right.Right = &TreeNode{Val: 7}
    fmt.Println(maxPathSum(root))
}

A 27

B 35

C 42

D 20

💡 Hint

Consider the path that includes nodes 15, 20, and 7 plus the root's right subtree.

The maximum path sum is 42, coming from the path 15 -> 20 -> 7 plus the root's right subtree. The path includes nodes with values 15, 20, and 7, summing to 42.

🧠 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 largest sum of values from any path starting at a leaf and ending at the root.

C The sum of all node values in the tree.

D The largest sum of values from any path between any two nodes, where the path may or may not pass through the root.

💡 Hint

The path can start and end at any nodes, not necessarily the root or leaves.

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 anywhere and does not have to pass through the root.

🔧 Debug

advanced

Identify the Bug in Maximum Path Sum Code

What error will the following Go code produce when calculating the maximum path sum in a binary tree?

DSA Go

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

var maxSum int

func maxPathSum(root *TreeNode) int {
    maxSum = 0
    maxGain(root)
    return maxSum
}

func maxGain(node *TreeNode) int {
    if node == nil {
        return 0
    }
    leftGain := max(maxGain(node.Left), 0)
    rightGain := max(maxGain(node.Right), 0)
    priceNewPath := node.Val + leftGain + rightGain
    if priceNewPath > maxSum {
        maxSum = priceNewPath
    }
    return node.Val + max(leftGain, rightGain)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    root := &TreeNode{Val: -3}
    fmt.Println(maxPathSum(root))
}

A Runtime panic due to nil pointer dereference

B Returns 0 instead of -3 due to incorrect maxSum initialization

C Compilation error due to missing return statement

D Returns -3 correctly

💡 Hint

Check the initial value of maxSum and how it affects negative values.

The variable maxSum is initialized to 0, so if all node values are negative, maxSum remains 0, which is incorrect. It should be initialized to the smallest integer to handle negative values properly.

📝 Syntax

advanced

Identify Syntax Error in Maximum Path Sum Code

Which option contains a syntax error in the Go code for maximum path sum?

DSA Go

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

var maxSum int

func maxPathSum(root *TreeNode) int {
    maxSum = -1 << 31
    maxGain(root)
    return maxSum
}

func maxGain(node *TreeNode) int {
    if node == nil {
        return 0
    }
    leftGain := max(maxGain(node.Left), 0)
    rightGain := max(maxGain(node.Right), 0)
    priceNewPath := node.Val + leftGain + rightGain
    if priceNewPath > maxSum {
        maxSum = priceNewPath
    }
    return node.Val + max(leftGain, rightGain)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    fmt.Println(maxPathSum(root))
}

A No syntax error; code compiles successfully

B Incorrect variable declaration for maxSum

C Using '<<' operator incorrectly for negative number initialization

D Missing closing brace in maxGain function

💡 Hint

Check if all braces and declarations are correct.

The code is syntactically correct and compiles successfully. The bit shift operator is valid for initializing maxSum to a very small integer.

🚀 Application

expert

Maximum Path Sum in Complex Tree Structure

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

DSA Go

Tree structure:
        -2
       /  \
      -1   3
          / \
         4  -5
        / 
       2

A 9

B 6

C 4

D 3

💡 Hint

Consider paths that include positive nodes and avoid negative sums where possible.

The maximum path sum is 9, coming from the path 2 -> 4 -> 3. Negative nodes are avoided to maximize the sum.

Practice

1. What does the term Maximum Path Sum in a binary tree mean?

easy

A. The largest sum of values along any path between two nodes in the tree

B. The sum of all node values in the tree

C. The sum of values from root to the leftmost leaf

D. The smallest sum of values along any path in the tree

Solution

1. Step 1: Understand the path definition

   The path can start and end at any two nodes, not necessarily root or leaf.

2. Step 2: Identify maximum sum meaning

   We look for the path with the highest total sum of node values.

3. Final Answer:

   The largest sum of values along any path between two nodes in the tree -> Option A

4. Quick Check:

   Maximum path sum means highest sum between any two nodes [OK]

Hint: Maximum path sum is any path with highest total node values [OK]

Common Mistakes:

• Thinking path must start at root
• Confusing maximum path sum with total tree sum
• Assuming path must end at leaf

2. Which of the following Go function signatures is correct for a function that calculates maximum path sum in a binary tree node defined as type TreeNode struct { Val int; Left, Right *TreeNode }?

easy

A. func maxPathSum(root *TreeNode) int

B. func maxPathSum(root TreeNode) int

C. func maxPathSum(root *TreeNode) *int

D. func maxPathSum(root *TreeNode) string

Solution

1. Step 1: Check parameter type

   Function should accept pointer to TreeNode to avoid copying the whole tree.

2. Step 2: Check return type

   Maximum path sum is an integer value, so return type should be int.

3. Final Answer:

   func maxPathSum(root *TreeNode) int -> Option A

4. Quick Check:

   Pointer input and int output for max path sum [OK]

Hint: Use pointer receiver and int return for tree max path sum [OK]

Common Mistakes:

• Passing TreeNode by value causing copies
• Returning pointer instead of int
• Returning string instead of int

3. Given the following Go code snippet, what is the printed output?

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func maxPathSum(root *TreeNode) int {
    maxSum := -1 << 31
    var maxGain func(node *TreeNode) int
    maxGain = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        leftGain := max(0, maxGain(node.Left))
        rightGain := max(0, maxGain(node.Right))
        priceNewPath := node.Val + leftGain + rightGain
        if priceNewPath > maxSum {
            maxSum = priceNewPath
        }
        return node.Val + max(leftGain, rightGain)
    }
    maxGain(root)
    return maxSum
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    root := &TreeNode{Val: -10}
    root.Left = &TreeNode{Val: 9}
    root.Right = &TreeNode{Val: 20}
    root.Right.Left = &TreeNode{Val: 15}
    root.Right.Right = &TreeNode{Val: 7}
    fmt.Println(maxPathSum(root))
}

medium

A. 27

B. 42

C. 35

D. 20

Solution

1. Step 1: Trace maxGain for each node

   Calculate max gain from left and right subtree ignoring negatives: - Node 9: maxGain = 9 - Node 15: maxGain = 15 - Node 7: maxGain = 7 - Node 20: maxGain = 20 + max(15,7) = 35 - Root -10: maxGain = -10 + max(9,35) = 25 Check maxSum updates: - At node 9: maxSum = 9 - At node 15: maxSum = 15 - At node 7: maxSum = 15 (unchanged) - At node 20: priceNewPath = 20 + 15 + 7 = 42, maxSum = 42 - At root: priceNewPath = -10 + 9 + 35 = 34 (maxSum stays 42)

2. Step 2: Return maxSum

   maxSum is 42 after full traversal.

3. Final Answer:

   42 -> Option B

4. Quick Check:

   Max path sum = 42 [OK]

Hint: Add node value plus max gains from left and right, track max sum [OK]

Common Mistakes:

• Not ignoring negative gains
• Returning max gain instead of max path sum
• Miscomputing path sums including negative nodes

4. The following Go function attempts to compute the maximum path sum in a binary tree but has a bug. What is the bug?

func maxPathSum(root *TreeNode) int {
    maxSum := -1 << 31
    var maxGain func(node *TreeNode) int
    maxGain = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        leftGain := maxGain(node.Left)
        rightGain := maxGain(node.Right)
        priceNewPath := node.Val + leftGain + rightGain
        if priceNewPath > maxSum {
            maxSum = priceNewPath
        }
        return node.Val + max(leftGain, rightGain)
    }
    maxGain(root)
    return maxSum
}

medium

A. It does not handle nil root

B. It returns maxSum before traversal

C. It does not ignore negative gains from left or right subtrees

D. It uses incorrect initial value for maxSum

Solution

1. Step 1: Analyze gain calculation

   The function uses leftGain and rightGain directly without ignoring negative values, which can reduce the path sum.

2. Step 2: Identify fix

   To fix, use max(0, leftGain) and max(0, rightGain) to ignore negative gains.

3. Final Answer:

   It does not ignore negative gains from left or right subtrees -> Option C

4. Quick Check:

   Negative gains must be ignored for correct max path sum [OK]

Hint: Always ignore negative subtree sums by max(0, gain) [OK]

Common Mistakes:

• Not ignoring negative subtree sums
• Wrong initial maxSum value
• Returning before traversal completes

5. You want to find the maximum path sum in a binary tree where some nodes have negative values. Which approach correctly handles this scenario? A) Use a recursive function that returns the maximum gain from each node, ignoring negative gains by taking max(0, gain), and update a global max sum including both left and right gains plus node value. B) Use a recursive function that sums all node values and returns the total. C) Use a breadth-first search to find the maximum node value and return it. D) Use a recursive function that only considers paths from root to leaf nodes.

hard

A. Consider only root-to-leaf paths recursively

B. Sum all node values recursively and return total

C. Find maximum node value using BFS and return it

D. Use recursion with max(0, gain) and update max sum including both children

Solution

1. Step 1: Understand negative values impact

   Negative node values can reduce path sums, so ignoring negative gains is necessary.

2. Step 2: Choose correct approach

   Use recursion with max(0, gain) and update max sum including both children uses recursion with max(0, gain) to ignore negative paths and updates max sum considering both left and right children plus current node, which correctly finds maximum path sum anywhere in the tree.

3. Final Answer:

   Use recursion with max(0, gain) and update max sum including both children -> Option D

4. Quick Check:

   Ignore negative gains and consider all paths for max sum [OK]

Hint: Ignore negative gains and consider all paths recursively [OK]

Common Mistakes:

• Summing all nodes ignoring path constraints
• Only considering root-to-leaf paths
• Returning max node value instead of path sum