Binary Tree Maximum Path Sum Interview Question for Meta

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Example 1:

Input: root = [1,2,3] Output: 6 Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

Input: root = [-10,9,20,null,null,15,7] Output: 42 Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Constraints:

The number of nodes in the tree is in the range [1, 3 * 10^4]. -1000 <= Node.val <= 1000

Maximum Path Sum in a Binary Tree

This problem asks us to find the maximum path sum in a binary tree, where a path is a sequence of nodes with adjacent nodes connected by an edge. A node can appear at most once in the path, and the path doesn't need to go through the root.

1. Naive Approach (Brute Force)

A brute-force approach would involve exploring all possible paths in the tree and calculating their sums, then returning the maximum sum found. This would be highly inefficient due to the exponential number of possible paths.

2. Optimal Approach (Recursion with Max Sum Tracking)

A more efficient approach uses recursion. For each node, we consider two possibilities:

The node is part of the maximum path that passes through it.
The node is not part of such a path.

We can calculate the maximum path sum passing through a node as the sum of the node's value and the maximum path sums from its left and right children (but only if these sums are positive, because we want to maximize the sum). We also need to keep track of the global maximum path sum found so far.

Here's the algorithm:

Initialize max_sum to negative infinity.
Define a recursive helper function max_path_sum_helper(node):
- Base case: If node is None, return 0.
- Recursively calculate left_sum and right_sum from the left and right children.
- Calculate max_single: the maximum path sum including the current node and at most one of its children: max(node.val + left_sum, node.val + right_sum, node.val)
- Calculate max_top: the maximum path sum including the current node and both of its children: node.val + left_sum + right_sum
- Update max_sum with the maximum of max_sum, max_single, and max_top.
- Return max_single (because the parent can only use one branch).
Call max_path_sum_helper(root).
Return max_sum.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxPathSum(root: TreeNode) -> int:
    max_sum = float('-inf')

    def max_path_sum_helper(node: TreeNode) -> int:
        nonlocal max_sum
        if not node:
            return 0

        left_sum = max(max_path_sum_helper(node.left), 0)
        right_sum = max(max_path_sum_helper(node.right), 0)

        max_single = max(node.val + left_sum, node.val + right_sum, node.val)
        max_top = node.val + left_sum + right_sum

        max_sum = max(max_sum, max_single, max_top)

        return max_single

    max_path_sum_helper(root)
    return max_sum


# Example Usage (Example 1)
root1 = TreeNode(1)
root1.left = TreeNode(2)
root1.right = TreeNode(3)
print(f"Max path sum for Example 1: {maxPathSum(root1)}")  # Output: 6

# Example Usage (Example 2)
root2 = TreeNode(-10)
root2.left = TreeNode(9)
root2.right = TreeNode(20)
root2.right.left = TreeNode(15)
root2.right.right = TreeNode(7)
print(f"Max path sum for Example 2: {maxPathSum(root2)}")  # Output: 42

# Example with a single node
root3 = TreeNode(-3)
print(f"Max path sum for single node: {maxPathSum(root3)}") #Output: -3

3. Big(O) Time Complexity Analysis

The time complexity is O(N), where N is the number of nodes in the binary tree. The max_path_sum_helper function visits each node exactly once.

4. Big(O) Space Complexity Analysis

The space complexity is O(H), where H is the height of the binary tree, due to the recursive call stack. In the worst-case scenario (skewed tree), H = N, making the space complexity O(N). In the best-case scenario (balanced tree), H = log(N), making the space complexity O(log(N)).

5. Edge Cases and Handling

Empty Tree: If the input tree is empty (root is None), the algorithm should return 0. (Handled implicitly as the helper function returns 0.)
All Negative Values: The algorithm correctly handles cases where all node values are negative. The max function ensures that even negative values are considered, and the global max_sum is updated accordingly.
Single Node Tree: If the tree contains only one node, the algorithm returns the value of that node.
Large Tree: The code is able to handle a tree of size 3 * 10^4 as it only goes through each node one time, and it uses constant extra space outside of the recursion.