Problem Statement

You are given the root of a binary tree.
A path in a tree is a sequence of nodes where each pair of adjacent nodes in the sequence has a parent-child relationship.

A path does not necessarily need to pass through the root, and it can start and end at any node.
The path sum is the sum of the values of the nodes in that path.

Your task is to find the maximum path sum among all possible paths in the given binary tree.

---

Example

Input:

     1
    / \
   2   3

Output:

6

Explanation:
The path 2 → 1 → 3 gives the maximum sum = 2 + 1 + 3 = 6.

---

Thinking About the Problem

We need to find the maximum possible sum of node values from any path in the binary tree.
The key challenge is that:

• A path can start and end anywhere in the tree.
• We cannot include both left and right children multiple times in different paths.
• At each node, the path can extend through the node or start anew.

The intuition is:

• For every node, the best path through that node can include:
  • The node’s value itself
  • The node’s value + maximum path from the left subtree
  • The node’s value + maximum path from the right subtree
  • The node’s value + left + right (if the node is the “root” of that path)

However, when returning to the parent node (upwards recursion), we can only choose one side (either left or right), because we can’t have a branching path upward.

So, at each step, we calculate:

• The maximum single-path sum that can be extended upwards.
• The maximum sum that can exist in any part of the tree (tracked globally).

---

Approach

1. Use a recursive function to calculate the maximum gain from each node.
2. For each node:
   • Compute the maximum path sum from its left subtree (ignore if negative).
   • Compute the maximum path sum from its right subtree (ignore if negative).
3. The local maximum path passing through the node = node.val + left + right.
4. Update the global maximum if this local maximum is higher.
5. Return to the parent the maximum gain from this node, which is:
   node.val + max(left, right)

This ensures that when moving up, we maintain a valid path (no branching).

---

Java Code Implementation

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

public class Solution {
    private int maxSum;

    public int maxPathSum(TreeNode root) {
        maxSum = Integer.MIN_VALUE;
        maxGain(root);
        return maxSum;
    }

    private int maxGain(TreeNode node) {
        if (node == null) return 0;

        // Ignore negative paths
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // Path sum including both left and right child
        int currentPathSum = node.val + leftGain + rightGain;

        // Update global max if needed
        maxSum = Math.max(maxSum, currentPathSum);

        // Return the max gain from one side to parent
        return node.val + Math.max(leftGain, rightGain);
    }
}

---

Step-by-Step Example

Let’s take the tree:

      -10
      /  \
     9   20
        /  \
       15   7

1. Starting from node 15 → maxGain(15) = 15
2. Node 7 → maxGain(7) = 7
3. Node 20 → leftGain = 15, rightGain = 7
   So currentPathSum = 20 + 15 + 7 = 42
   Update maxSum = 42, return to parent 20 + max(15, 7) = 35.
4. Node 9 → maxGain(9) = 9
5. Node -10 → leftGain = 9, rightGain = 35
   So currentPathSum = -10 + 9 + 35 = 34
maxSum remains 42.

Final answer: 42

---

Time and Space Complexity

• Time Complexity: O(N), because we visit each node once.
• Space Complexity: O(H), where H is the height of the tree (recursion stack).

---

Key Takeaways

• The problem requires handling paths that don’t necessarily include the root.
• Always discard negative path sums when propagating upward.
• Keep a global variable to track the overall maximum path sum.
• This is a post-order traversal problem (left → right → root).