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.