SyntaxPilot
Courses/DSA and Coding Problems/Lesson 40
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 40 of 90

Binary tree maximum path sum (hard)

queued

These are the notes for DSA episode 40. The problem is marked hard, but it is the same pattern as episode 37 (diameter of a binary tree): one postorder pass that returns one value up to the parent and updates a global maximum on the way. Here the value is a sum instead of a height. We start from a real-life road trip, define every word (path, path sum, top of a path, gain, negative values), solve it the obvious way (try every node as the top, O(n · h)), watch it hit Time Limit Exceeded on a big tree, and then solve it in O(n). Every program below was run with javac 21 with an 8-second limit (like the SyntaxPilot compiler), and every output shown is real.

The problem, in real life

You are planning a road trip. The towns are joined by roads, and the map has a special shape: between any two towns there is exactly one route, no loops. That shape is a tree. You are a musician: some towns hold a fair and pay you (+15, +20); some towns charge a toll to pass through (−10). You may start in any town and end in any town, but you can never visit a town twice. Which trip earns the most money?

On the road trip In a binary tree
A town a node
The money a town pays (or charges) the node's value (can be negative)
A road between two towns an edge
Your trip, no town twice a path
The money you end with the path sum
The highest town on your trip (closest to the capital) the top of the path
The best money from a town going only "away from the capital" the gain of a node
Not taking a toll road at all clamping a negative gain to 0

The freedom to start and end anywhere is what makes the problem hard: the best trip need not touch the root, and need not reach a leaf.

Every word, from zero

  • Binary tree, node, edge, root, parent, child, leaf: from episode 36. A node has a value val and up to two children, left and right; null means "no child".
  • Path: a sequence of nodes where each node is joined to the next by an edge, and no node appears twice. A path has at least one node. It may start and end anywhere; it need not include the root or a leaf.
  • Path sum: the total of the values of the nodes on the path.
  • Negative values: a node can be worth less than zero (a toll). Then the best path may stop before it.
  • Top of a path: the node of the path that is closest to the root. Every path has exactly one top. The path goes up from one side to the top, then down the other side (like a mountain road over a pass). Either side may be empty.
  • Fork: a set of nodes where one node would need three edges in the path (two children and its parent). A fork is not a path.
  • Gain of a node: the best sum of a path that starts at that node and goes straight down, choosing one child at each step (or stopping). For a leaf, gain = its value.
  • Clamping: replacing a negative number by 0, with Math.max(0, x). A negative gain means "don't go down there", which is worth 0.
  • Postorder: visit left subtree, right subtree, then the node (episode 36). It lets each node use its children's answers.
  • Global maximum: a variable outside the recursion (static int best) that every call can update.

Our familiar tree from episode 36:

        1
      /   \
     2     3
    / \     \
   4   5     6
Nodes Path? Top Sum
4 → 2 → 5 yes 2 11
5 → 2 → 1 → 3 → 6 yes (the best here) 1 17
6 yes (one node) 6 6
4, 5, 2, 1 no: 2 would use three edges (a fork)

Problem statement

Binary Tree Maximum Path Sum (LeetCode 124). Given the root of a non-empty binary tree, return the maximum path sum of any path. Values are between −1000 and 1000; LeetCode's trees have up to 3 · 10^4 nodes.

[1, 2, 3]                          →  6    (2 → 1 → 3)
[-10, 9, 20, null, null, 15, 7]    →  42   (15 → 20 → 7, skips the root)
[-3]                               →  -3   (one node: the path cannot be empty)

The array form is level order with null for missing children: [-10, 9, 20, null, null, 15, 7] is

      -10
      /  \
     9    20
         /  \
        15   7

In Java we build the examples directly:

        Node a = new Node(1, new Node(2), new Node(3));
        Node b = new Node(-10, new Node(9),
                          new Node(20, new Node(15), new Node(7)));
        Node c = new Node(-3);

Brute force: try every node as the top

Every path has exactly one top. So for every node n, compute the best straight-down sum on its left and on its right with a fresh recursion down(), clamp each at 0, and form n.val + L + R. The answer is the largest of these.

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int down(Node n) {
        if (n == null) return 0;
        int best = Math.max(down(n.left), down(n.right));
        return n.val + Math.max(0, best);
    }
    static int bruteMax(Node n) {
        if (n == null) return Integer.MIN_VALUE;
        int L = Math.max(0, down(n.left));
        int R = Math.max(0, down(n.right));
        int top = n.val + L + R;
        return Math.max(top, Math.max(bruteMax(n.left), bruteMax(n.right)));
    }
    public static void main(String[] args) {
        Node a = new Node(1, new Node(2), new Node(3));
        Node b = new Node(-10, new Node(9),
                          new Node(20, new Node(15), new Node(7)));
        Node c = new Node(-3);
        System.out.println(bruteMax(a));
        System.out.println(bruteMax(b));
        System.out.println(bruteMax(c));
    }
}

Real output:

6
42
-3

Correct on all three examples. Integer.MIN_VALUE (−2,147,483,648, the smallest int) is returned for an empty subtree so it never wins the Math.max.

A big tree: Time Limit Exceeded

A chain of 6,000 nodes (each the left child of the previous one), with a complete tree 20 levels deep (2^20 − 1 ≈ 10 lakh nodes) hung at the bottom. Values are random in −100 .. 100 (new Random(40), so every run builds the same tree).

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int down(Node n) {
        if (n == null) return 0;
        int best = Math.max(down(n.left), down(n.right));
        return n.val + Math.max(0, best);
    }
    static int bruteMax(Node n) {
        if (n == null) return Integer.MIN_VALUE;
        int L = Math.max(0, down(n.left));
        int R = Math.max(0, down(n.right));
        int top = n.val + L + R;
        return Math.max(top, Math.max(bruteMax(n.left), bruteMax(n.right)));
    }
    static Random rnd = new Random(40);
    static int r() { return rnd.nextInt(201) - 100; }
    static Node full(int d) {
        if (d == 0) return null;
        return new Node(r(), full(d - 1), full(d - 1));
    }
    static Node bigTree() {
        Node root = new Node(r()), cur = root;
        for (int i = 1; i < 6000; i++) {
            cur.left = new Node(r());
            cur = cur.left;
        }
        cur.left = full(20);
        return root;
    }
    public static void main(String[] args) {
        Node big = bigTree();
        long t0 = System.nanoTime();
        int ans = bruteMax(big);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println("best = " + ans + ", " + ms + " ms");
    }
}

Real result in the compiler: Time Limit Exceeded (killed at 8 s). Run locally without a limit it printed best = 3505, 34401 ms (and 36892 ms on a second run): more than 30 seconds.

Why the brute force is slow

down(n) walks every node below n. bruteMax calls it for every node, so a node is walked once by each of its ancestors. The ten lakh bottom nodes have more than 6,000 ancestors each: about 6,000 × 10,00,000 ≈ 600 crore (6 billion) node visits. In general the cost is the sum of all subtree sizes, which is O(n · h) for n nodes and height h; on a plain chain h = n, so it is O(n²).

The waste: node 20 computes its gain from 15 and 7; then its parent asks 20 again, which asks 15 and 7 again. Each node should compute its gain once and hand it up.

The key insight: one postorder pass

This is the diameter pattern from episode 37 (there: return the height up, update the best diameter). Here, for every node n, after both children have answered:

  1. L = max(0, gain(left)), R = max(0, gain(right)): a negative branch is a toll road, so it is worth 0 (don't take it).
  2. As the top, the path can use both sides: best = max(best, n.val + L + R).
  3. To the parent, return one side only: n.val + max(L, R). If the path continues up to the parent, it cannot also fork into both children.

Both sides to update the answer, one side to return.

Trace on example 2:

Node (postorder) L R as the top: val + L + R best returns val + max(L, R)
9 0 0 9 9 9
15 0 0 15 15 15
7 0 0 7 15 7
20 15 7 42 42 35
−10 9 35 34 42 25

Answer 42: the path 15 → 20 → 7, which never touches the root. The global best caught it at node 20.

The optimal solution in Java

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int best;
    static int gain(Node n) {
        if (n == null) return 0;
        int L = Math.max(0, gain(n.left));
        int R = Math.max(0, gain(n.right));
        best = Math.max(best, n.val + L + R);
        return n.val + Math.max(L, R);
    }
    static int maxPathSum(Node root) {
        best = Integer.MIN_VALUE;
        gain(root);
        return best;
    }
    public static void main(String[] args) {
        Node a = new Node(1, new Node(2), new Node(3));
        Node b = new Node(-10, new Node(9),
                          new Node(20, new Node(15), new Node(7)));
        Node c = new Node(-3);
        Node d = new Node(-2, new Node(-1), new Node(-3));
        Node e = new Node(10, new Node(-20, new Node(15), null), null);
        System.out.println(maxPathSum(a));
        System.out.println(maxPathSum(b));
        System.out.println(maxPathSum(c));
        System.out.println(maxPathSum(d));
        System.out.println(maxPathSum(e));
    }
}

Real output:

6
42
-3
-1
15
  • a, b, c: the three LeetCode examples.
  • d (−2 with children −1 and −3, all negative): −1, just the least bad node.
  • e (a chain 10 → −20 → 15): 15. The whole chain is only 10 − 20 + 15 = 5, so the best trip is the town 15 alone.

The big tree in milliseconds

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int best;
    static int gain(Node n) {
        if (n == null) return 0;
        int L = Math.max(0, gain(n.left));
        int R = Math.max(0, gain(n.right));
        best = Math.max(best, n.val + L + R);
        return n.val + Math.max(L, R);
    }
    static int maxPathSum(Node root) {
        best = Integer.MIN_VALUE;
        gain(root);
        return best;
    }
    static Random rnd = new Random(40);
    static int r() { return rnd.nextInt(201) - 100; }
    static Node full(int d) {
        if (d == 0) return null;
        return new Node(r(), full(d - 1), full(d - 1));
    }
    static Node bigTree() {
        Node root = new Node(r()), cur = root;
        for (int i = 1; i < 6000; i++) {
            cur.left = new Node(r());
            cur = cur.left;
        }
        cur.left = full(20);
        return root;
    }
    public static void main(String[] args) {
        Node big = bigTree();
        long t0 = System.nanoTime();
        int ans = maxPathSum(big);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println("best = " + ans + ", " + ms + " ms");
    }
}

Real output: best = 3505, 13 ms (12 to 16 ms over several runs). The same answer as the brute force, which needed more than 30 seconds.

The same solution in C++

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int v, Node* l = nullptr, Node* r = nullptr) : val(v), left(l), right(r) {}
};

int best;
int gain(Node* n) {
    if (!n) return 0;
    int L = max(0, gain(n->left));
    int R = max(0, gain(n->right));
    best = max(best, n->val + L + R);
    return n->val + max(L, R);
}
int maxPathSum(Node* root) {
    best = INT_MIN;
    gain(root);
    return best;
}

int main() {
    Node* a = new Node(1, new Node(2), new Node(3));
    Node* b = new Node(-10, new Node(9), new Node(20, new Node(15), new Node(7)));
    Node* c = new Node(-3);
    Node* d = new Node(-2, new Node(-1), new Node(-3));
    Node* e = new Node(10, new Node(-20, new Node(15)));
    for (Node* t : {a, b, c, d, e}) cout << maxPathSum(t) << '\n';
}

Compiled with g++ -O2 -std=c++17. Real output:

6
42
-3
-1
15

INT_MIN plays the role of Integer.MIN_VALUE.

The same solution in Python

import sys
sys.setrecursionlimit(100000)

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

def max_path_sum(root):
    best = float("-inf")
    def gain(n):
        nonlocal best
        if n is None:
            return 0
        L = max(0, gain(n.left))
        R = max(0, gain(n.right))
        best = max(best, n.val + L + R)
        return n.val + max(L, R)
    gain(root)
    return best

a = Node(1, Node(2), Node(3))
b = Node(-10, Node(9), Node(20, Node(15), Node(7)))
c = Node(-3)
d = Node(-2, Node(-1), Node(-3))
e = Node(10, Node(-20, Node(15)))
for t in (a, b, c, d, e):
    print(max_path_sum(t))

Real output:

6
42
-3
-1
15

nonlocal best lets the inner function update the variable of max_path_sum. Python's default recursion limit is 1000; on a 5,000-node chain without sys.setrecursionlimit it fails with RecursionError: maximum recursion depth exceeded.

Three real bugs

Bug 1: returning both sides to the parent

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int best;
    static int gain(Node n) {
        if (n == null) return 0;
        int L = Math.max(0, gain(n.left));
        int R = Math.max(0, gain(n.right));
        best = Math.max(best, n.val + L + R);
        return n.val + L + R;
    }
    static int maxPathSum(Node root) {
        best = Integer.MIN_VALUE;
        gain(root);
        return best;
    }
    public static void main(String[] args) {
        Node t = new Node(1, new Node(2, new Node(4), new Node(5)),
                             new Node(3, null, new Node(6)));
        System.out.println(maxPathSum(t));
    }
}

Real output: 21. The right answer for this tree is 17 (5 → 2 → 1 → 3 → 6). Node 2 returned 2 + 4 + 5 = 11 (a fork), node 3 returned 9, and the root formed 1 + 11 + 9 = 21, which is the set {4, 5, 2, 1, 3, 6}: not a path. Fix: return n.val + Math.max(L, R);.

Bug 2: starting best at 0

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int best;
    static int gain(Node n) {
        if (n == null) return 0;
        int L = Math.max(0, gain(n.left));
        int R = Math.max(0, gain(n.right));
        best = Math.max(best, n.val + L + R);
        return n.val + Math.max(L, R);
    }
    static int maxPathSum(Node root) {
        best = 0;
        gain(root);
        return best;
    }
    public static void main(String[] args) {
        System.out.println(maxPathSum(new Node(-3)));
        System.out.println(maxPathSum(new Node(-2, new Node(-1), new Node(-3))));
    }
}

Real output:

0
0

The answers are −3 and −1. Zero is the sum of the empty path, which is not allowed, and no real path ever beats it in an all-negative tree. Fix: best = Integer.MIN_VALUE;.

Bug 3: not clamping negative gains

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int best;
    static int gain(Node n) {
        if (n == null) return 0;
        int L = gain(n.left);
        int R = gain(n.right);
        best = Math.max(best, n.val + L + R);
        return n.val + Math.max(L, R);
    }
    static int maxPathSum(Node root) {
        best = Integer.MIN_VALUE;
        gain(root);
        return best;
    }
    public static void main(String[] args) {
        System.out.println(maxPathSum(new Node(5, new Node(-8), new Node(4))));
    }
}

Real output: 4. The right answer is 5 + 4 = 9. Without Math.max(0, ...), node 5 was forced to take the −8 branch: −8 + 5 + 4 = 1, so the best found was the single node 4. Fix: int L = Math.max(0, gain(n.left)); (and the same for R).

Also: very deep trees

Recursion uses one stack frame per level. With Java's default stack, the optimal gain on a chain worked at 20,000 levels and failed at 22,000 (and at 50,000) with:

Exception in thread "main" java.lang.StackOverflowError
    at Main.gain(Main.java:6)

Our big tree is about 6,000 levels deep, so it is safe. For deeper trees use an iterative postorder (practice question 4) or run the work in a Thread with a bigger stack size.

Complexity

Approach Time Extra space Big tree (6,000-chain + 10 lakh nodes)
Every node as the top, fresh down() calls O(n · h), O(n²) on a chain O(h) recursion more than 30 s: TLE
One postorder pass (gain + global best) O(n) O(h) recursion about 15 ms

h is about log₂ n for a balanced tree and n for a chain.

Common mistakes

Mistake What you see Why Fix
return n.val + L + R; 21 instead of 17 a fork is sent up to the parent return n.val + Math.max(L, R);
best = 0; 0 instead of -3 (and -1) the empty path is not allowed best = Integer.MIN_VALUE;
int L = gain(n.left); (no clamp) 4 instead of 9 negative branches are forced into the path Math.max(0, gain(n.left))
Only considering paths through the root 34 instead of 42 on example 2 the best path may skip the root update best at every node
Recursion on a 22,000+ level chain java.lang.StackOverflowError one stack frame per level iterative postorder, or a bigger thread stack
Python without a raised limit RecursionError: maximum recursion depth exceeded default limit 1000 sys.setrecursionlimit(...) or iterative
Forgetting to reset best between calls a later tree can report an earlier tree's answer best is static set it in maxPathSum before calling gain

Mini project: the road-trip planner

Make a Town node with a String name and an int money. Build a small map as a binary tree (say 8 towns, some paying, some charging tolls). Print the best trip as a route of names and its total, for example Fairpur → Melaganj → Tollnagar → ... = 42. Hint: practice question 1 returns the path itself. Then print, for every town, its gain (the best trip that starts there and heads away from the capital).

Practice

  1. Return the best path itself, not only its sum.
Solution

Make the recursion return the best straight-down path as a list (top first). At each node, if n.val + L + R beats best, build the path: the left list reversed (if L > 0), then n.val, then the right list (if R > 0). Return n.val followed by the better child's list (if it is positive).

    static int best;
    static List<Integer> bestPath;
    static List<Integer> down(Node n) {           // best straight-down path, top first
        if (n == null) return new ArrayList<>();
        List<Integer> l = down(n.left), r = down(n.right);
        int L = Math.max(0, sum(l)), R = Math.max(0, sum(r));
        if (n.val + L + R > best) {
            best = n.val + L + R;
            List<Integer> p = new ArrayList<>();
            if (L > 0) { p.addAll(l); Collections.reverse(p); }
            p.add(n.val);
            if (R > 0) p.addAll(r);
            bestPath = p;
        }
        List<Integer> up = new ArrayList<>();
        up.add(n.val);
        if (Math.max(L, R) > 0) up.addAll(L >= R ? l : r);
        return up;
    }
    static int sum(List<Integer> p) { int s = 0; for (int x : p) s += x; return s; }

Real output (with best = Integer.MIN_VALUE before each call): example 2 → 42 [15, 20, 7], the episode-36 tree → 17 [5, 2, 1, 3, 6]. (Summing the lists makes it O(n · h); to stay O(n), return the gain alongside the list.)

  1. Maximum root-to-leaf path sum (the path must start at the root and end at a leaf).
Solution

Only one branch, no global needed, and no clamping (you must reach a leaf):

    static int rootToLeaf(Node n) {
        if (n.left == null && n.right == null) return n.val;
        int b = Integer.MIN_VALUE;
        if (n.left != null) b = Math.max(b, rootToLeaf(n.left));
        if (n.right != null) b = Math.max(b, rootToLeaf(n.right));
        return n.val + b;
    }

Real output: example 2 → 25 (−10 → 20 → 15), the episode-36 tree → 10 (1 → 3 → 6).

  1. Longest univalue path (LeetCode 687): the longest path (in edges) where all nodes have the same value.
Solution

The same "both sides for the answer, one side to return" pattern. A child's arm counts only if its value equals the node's value.

    static int longest;
    static int uni(Node n) {
        if (n == null) return 0;
        int l = uni(n.left), r = uni(n.right);
        int L = (n.left != null && n.left.val == n.val) ? l + 1 : 0;
        int R = (n.right != null && n.right.val == n.val) ? r + 1 : 0;
        longest = Math.max(longest, L + R);
        return Math.max(L, R);
    }

For the tree 5 → (4 → 1, 1), (5 → right 5) the real output is 2 (5 → 5 → 5).

  1. Maximum path sum without recursion (safe on any depth).
Solution

Collect the nodes with a stack in "node, then children" order; reading that list backwards visits every child before its parent. Store each node's gain in a map.

    static int iterMax(Node root) {
        Map<Node, Integer> g = new HashMap<>();
        Deque<Node> st = new ArrayDeque<>();
        List<Node> order = new ArrayList<>();
        st.push(root);
        while (!st.isEmpty()) {
            Node n = st.pop();
            order.add(n);
            if (n.left != null) st.push(n.left);
            if (n.right != null) st.push(n.right);
        }
        int ans = Integer.MIN_VALUE;
        for (int i = order.size() - 1; i >= 0; i--) {   // children before parents
            Node n = order.get(i);
            int L = Math.max(0, g.getOrDefault(n.left, 0));
            int R = Math.max(0, g.getOrDefault(n.right, 0));
            ans = Math.max(ans, n.val + L + R);
            g.put(n, n.val + Math.max(L, R));
        }
        return ans;
    }

Real output: example 2 → 42, the episode-36 tree → 17, and a chain of 1,00,000 nodes of value 1 → 100000 (no StackOverflowError). g.getOrDefault(null, 0) returns 0 for a missing child, since HashMap allows a null key lookup.

Quick quiz

In example 2 (-10 → 9, (20 → 15, 7)), what does gain(20) return to its parent: 42, 35, 27 or 20?

Answer

35 = 20 + max(15, 7). The parent can continue down only one branch. 42 uses both branches, so it only updates best; it never goes up.

Interview questions

  1. Why does gain return one branch but best use two? A path that continues to the parent can enter this node from only one child; a path whose top is this node can use both children.
  2. Why clamp at 0? A negative gain lowers any sum it is added to, so "don't go down that side" (worth 0) is always at least as good.
  3. Why initialise best to Integer.MIN_VALUE, not 0? The path must contain at least one node; in an all-negative tree every path is negative.
  4. Time and space? O(n) time (each node once, constant work), O(h) space for the recursion.
  5. How is this related to the diameter problem? Same structure: postorder, return one arm (height / gain) up, update a global with both arms (left + right edges / L + val + R).
  6. What if the tree has 10^5 levels? Recursion can overflow the stack (StackOverflowError in Java, RecursionError in Python); use an iterative postorder.
  7. Can the answer overflow int? Not under LeetCode's limits (3 · 10^4 nodes × 1000 = 3 · 10^7). With bigger values or counts, use long.

Glossary

Term Meaning
Binary tree A tree where every node has at most two children, left and right
Node / value One item of the tree; here it holds an int val that may be negative
Edge The link between a parent and a child
Path Nodes joined by edges one after another, no node twice, at least one node
Path sum The sum of the values of the nodes on a path
Top of a path The node of the path closest to the root; the path goes up to it, then down
Fork Three edges meeting at one node of the chosen set; not a path
Gain The best sum of a path that starts at a node and goes straight down (one child per step)
Clamping Replacing a negative value by 0: Math.max(0, x)
Postorder Left subtree, right subtree, then the node; children answer first
Global maximum A variable outside the recursion (static int best) updated by every call
Integer.MIN_VALUE The smallest Java int, −2,147,483,648; a safe starting value for a maximum
Brute force The obvious, slow method: here, every node as the top with fresh recursive calls
O(n · h), O(n²) Running time growing with nodes × height; squared on a chain
Time Limit Exceeded (TLE) The program was stopped for running too long (8 s in the SyntaxPilot compiler)
StackOverflowError Java's error when recursion goes too deep for the call stack
RecursionError Python's error when recursion passes the recursion limit (default 1000)

Summary

  • A path is connected nodes, no node twice, at least one node; it may skip the root. Every path has one top.
  • Gain of a node = best straight-down sum from it: val + max(0, gain(left), gain(right)).
  • Brute force (every node as the top, fresh calls) is O(n · h): TLE on a tall tree.
  • One postorder pass: clamp children's gains at 0, best = max(best, val + L + R) (both sides), return val + max(L, R) (one side). Start best at Integer.MIN_VALUE. O(n) time, O(h) space.

Next episode: Serialize and deserialize a binary tree (hard).