NUHMAN.com

Introduction

LeetCode 124: Binary Tree Maximum Path Sum is a popular problem that challenges you to find the maximum sum of a path in a binary tree. The path can start and end at any node in the tree, and it can move along any parent-child connection. The goal is to compute the maximum possible sum of values along the path.

This problem requires careful handling of the tree structure and can be solved using a Depth-First Search (DFS) approach with recursion. During traversal, we keep track of the maximum sum at each node and update the result when necessary.

Problem Statement

Given a non-empty binary tree, find the maximum path sum. A path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path sum is the sum of the node values along the path.

Example:

go

Input: 
       1
      / \
     2   3

Output: 6
Explanation: The optimal path is 2 -> 1 -> 3, with a sum of 6.

Approach:

To solve this problem, we will use Depth First Search (DFS) to explore each node and calculate the maximum path sum. At each node, we have two possible cases to consider:

1. The path that includes the current node and moves towards its left child.
2. The path that includes the current node and moves towards its right child.

At each step, we compute the maximum possible path sum that can be obtained from the current node to its left or right child. Then, we update the global maximum path sum whenever the sum including the current node exceeds the previously recorded maximum sum.

Steps:

1. Start with a DFS traversal of the tree. For each node, calculate the maximum path sum starting from that node and extend to either the left or the right child.
2. At each node, compute the maximum sum that can be obtained from the left and right children.
3. Keep track of the maximum path sum for the tree so far.
4. Return the maximum path sum after the DFS traversal is complete.

Key Considerations:

• If a node’s left or right child results in a negative path sum, ignore it (i.e., do not include the child).
• The result may include a path that starts and ends at the same node, so we must keep track of both local and global maximum sums.

Go Implementation

Solution Using Depth First Search (DFS)

go

package main

import "fmt"

// Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// maxPathSum calculates the maximum path sum for a binary tree.
func maxPathSum(root *TreeNode) int {
    maxSum := -1 << 63 // Initialize maxSum to the minimum possible value
    
    // Helper function for DFS
    var dfs func(node *TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0 // If the node is nil, return 0 (no contribution to the path sum)
        }
        
        // Recursively calculate the maximum path sum for left and right subtrees
        left := max(dfs(node.Left), 0)  // If left path is negative, discard it
        right := max(dfs(node.Right), 0) // If right path is negative, discard it
        
        // Update the global maxSum with the current node’s value plus both subtrees
        maxSum = max(maxSum, node.Val + left + right)
        
        // Return the maximum sum path that can be extended upwards (either left or right path)
        return node.Val + max(left, right)
    }
    
    // Perform DFS starting from the root
    dfs(root)
    
    return maxSum // Return the global maximum path sum
}

// max is a helper function to return the maximum of two integers.
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    // Constructing a binary tree:
    //         -10
    //        /    \
    //       9     20
    //            /  \
    //           15   7
    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}
    
    result := maxPathSum(root)
    fmt.Println(result) // Output: 42
}

Explanation:

1. TreeNode Definition:

• We define a TreeNode struct with Val for the value of the node, and Left and Right for the left and right child pointers, respectively.

1. DFS Function:

• The helper function dfs is defined recursively to calculate the maximum path sum starting from a given node. The DFS is performed on the left and right children of each node.
• If the node is nil, it returns 0 (since no path exists).
• For each node, the maximum path sum is calculated from the left and right children, and the global maxSum is updated.

1. Max Function:

• The max function is a utility to return the maximum of two values, used to decide whether to include the left or right path in the current node's path sum.

1. Main Function:

• We construct a sample binary tree and call the maxPathSum function to calculate the maximum path sum. The result is printed to the console.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(h)

Time Complexity:

• The time complexity is O(n), where n is the number of nodes in the binary tree. We traverse each node exactly once.

Space Complexity:

• The space complexity is O(h), where h is the height of the tree. This is due to the recursive DFS calls, which use the call stack. In the worst case, the tree is completely unbalanced, and the space complexity is O(n). For a balanced tree, the space complexity is O(log n).

Edge Cases

1. Edge Case: Empty Tree

• Input: nil
• Output: 0
• Explanation: An empty tree has no nodes, so the maximum path sum is 0.

1. Edge Case: Single Node

• Input: [1]
• Output: 1
• Explanation: A single node tree has the node value as the maximum path sum.

1. Edge Case: All Negative Values

• Input: [-10, -5, -20]
• Output: -5
• Explanation: In cases with negative values, the maximum path sum might be achieved by picking the highest single node.

1. Edge Case: Path Including Negative Nodes

• Input: [-10, 9, 20, 15, 7]
• Output: 42
• Explanation: Even with negative nodes, the path sum can be maximized by excluding the negative path parts.

Conclusion

LeetCode 124: Binary Tree Maximum Path Sum is an interesting and challenging problem that combines depth-first search (DFS) with dynamic programming concepts. By calculating the maximum path sum at each node and updating a global variable, we can efficiently compute the maximum possible path sum for the entire tree. The solution runs in O(n) time, making it optimal for large trees, and uses O(h) space, where h is the height of the tree.