Here is solutions for Binary Tree Maximum Path Sum.

1. Understand the problem

• You’re given the root of a binary tree (values can be negative).

• A path is defined as any sequence of nodes where:

  • Each pair of consecutive nodes in the sequence are connected by an edge.

  • A path can start and end at any nodes in the tree.

  • You cannot revisit a node (no cycles).

  • The path does not have to go through the root.

  • The path can go like left-child → parent → right-child (i.e. it can “turn” at a node).

• Each path has a sum = sum of the node values along the path.

• Goal: Return the maximum path sum over all possible paths in the tree.

Classic examples:

• If all numbers are positive → best path likely uses many nodes.

• If all numbers are negative → best path is just the maximum single node.

2. Clarify constraints, asks 4 - 5 questions including edge cases.

1. Can node values be negative?

• Yes, they can be positive, zero, or negative (e.g. -1000 to 1000).

1. Is the tree guaranteed to be non-empty?

• Yes, there is at least one node.

1. Does the path have to start at the root or end at a leaf?

• No. It can start/end anywhere as long as nodes are connected and no node is repeated.

1. Can the path go “up and then down” (like left child → parent → right child)?

• Yes. That’s actually the key case: a node can be the “turning point” of the best path.

1. What’s the expected tree size / constraints?

• Typical: 1 <= number of nodes <= 10^4 (or similar).

• That means we need about O(n) or O(n log n), not O(n^2) in worst case

3. Explore examples.

1. Example 1

      1
     / \
    2   3

All paths and sums:

• [2] = 2

• [3] = 3

• [1] = 1

• 2 → 1 = 3

• 1 → 3 = 4

• 2 → 1 → 3 = 6 ← maximum

Answer: 6

1. Example 2

      -10
      /  \
     9   20
         / \
        15  7

• Possible best path: 15 → 20 → 7

• Sum = 15 + 20 + 7 = 42

Other candidates (for sanity):

• 9 alone = 9

• -10 + 9 = -1

• 20 + 15 = 35

• 20 + 7 = 27

• 9 + (-10) + 20 = 19

Answer: 42

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. Naive solution - Time O(N^2), Space O(N)

• Enumerate all possible paths and compute their sums. For each pair of nodes, try to find the max path passing through them, etc.

• You’d need to consider:

  • paths starting and ending at arbitrary nodes

  • up to O(n^2) paths.

• Time: O(N^2).

• Space: O(N).

4.2. DFS with “max-gain” in each node - Time O(N), Space O(N)

max_gain(node) = node.val + max(0, left_gain) + max(0, right_gain)

• Time: O(N)

• Space: O(H)

5. Implement solutions.

5.1. Naive Solution - Depth First Search - Time O(N^2), Space O(H)

• Max path at node i = node + max_path from left + max_path from right

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        res = -float('inf')
        def dfs(root):
            nonlocal res
            if not root:
                return
            left = self.getMax(root.left)
            right = self.getMax(root.right)
            res =max(res, root.val + left + right)
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        return res

    def getMax(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        left = self.getMax(root.left)
        right = self.getMax(root.right)
        path = root.val + max(left, right)
        return max(0, path)

• Time: O(N^2)

• Space: O(H)

5.2. Depth First Search (Optimal) - Time O(N), Space 0(H)

Idea:

• Same idea but store directly to value.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        res = [root.val]

        def dfs(root):
            if not root:
                return 0

            leftMax = dfs(root.left)
            rightMax = dfs(root.right)
            leftMax = max(leftMax, 0)
            rightMax = max(rightMax, 0)

            res[0] = max(res[0], root.val + leftMax + rightMax)
            return root.val + max(leftMax, rightMax)

        dfs(root)
        return res[0]

• Time: O(N)

• Space: 0(H)

6. Dry run testcases.

Example 1:

      1
     / \
    2   3