The O(n) Club: Binary Tree Maximum Path Sum, Now With Extra Chaos

The O(n) Club: Binary Tree Maximum Path Sum, Now With Extra Chaos

⚡ TL;DR

Hunt for the highest-sum path in your binary tree. This path can start and end wherever—and yes, it can tiptoe around the root if the root is acting negative. Brute force is wildly impractical (O(n²)), so unleash your inner DFS wizard and only let one branch propagate upward.
Here’s a Java whiff to get the scent:

// Brute force: Try every path; regret your career choices.
// Smart: For each node, compute the best upward path and 'local party' sum; update your global best.
int maxPathSum(TreeNode root) {
    max = Integer.MIN_VALUE;
    dfs(root);
    return max;
}

🧠 How Devs Usually Mess This Up

Classic rookie moves:

🔍 What’s Actually Going On

Picture: Each node is a party house. You peek left and right for loot (or danger), and if this is where the party truly peaks, you can combine your value with both sides (forming a glorious ‘V’). But if you need to keep the party rolling upward to your parent, you can only take one branch (fire hazard otherwise).
Globally, you want to keep track of the best one-night bash found anywhere—you don’t need to return through the root or RSVP at any particular door.

🛠️ PseudoCode

• For each node:
  • Recursively find the highest ‘path-up’ sum from the left and right kids (ignore negatives—no bad juju).
• At the node:
  • Calculate: node.val + leftMax + rightMax (the ‘V’ party score right here).
  • Update your global best if it’s a new record-breaker.
• Return upward:
  • Node’s value + max(leftMax, rightMax). You can’t bring both branches up the parent tree.