#37 · Trees

Binary Tree Maximum Path Sum

A path is a sequence of nodes where each adjacent pair is connected by an edge; it need not pass through the root. Return the maximum sum of node values over all non-empty paths in the tree.

HardLeetCode

Current node
On the path / call stack
Done / found
Rejected
Temporary thread (Morris)

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Binary tree path structure

Every path has a unique highest node (its "top"). From the top, it goes down at most once into the left subtree and at most once into the right subtree. So a path is "left chain + top + right chain", where each chain is a downward walk.

Memory layout

Pointer-linked nodes. The algorithm needs per-node results (a gain) that flow from children to parent, which a post-order traversal provides.

Operation	Cost
post-order pass over all nodes	O(n)
extra space	O(h) for the stack

Downward gain (what a parent can use)

gain(n) = n.val + max(0, gain(left), gain(right)): the best sum of a chain that STARTS at n and goes down one branch. A parent can extend a chain through n but cannot use both children of n (a path cannot fork). Negative gains are dropped (clamped to 0) because leaving a branch out is always allowed.

Memory layout

One integer per node, either returned up the call stack or stored in a table.

Operation	Cost
compute gain(n) from children	O(1)

Why it fits

The best path through a node depends only on the best downward chains of its two children, which is exactly the information a post-order traversal has when it reaches the node.
Two different quantities must be tracked: the best path bending at a node (uses BOTH children: candidate answer) and the gain handed to the parent (uses only ONE child). Mixing them up is the classic bug.
Clamping child gains at 0 handles negative values elegantly: an unhelpful branch is simply not extended.

Why alternatives degrade

Try every pair of nodes as endpoints:: O(n²) pairs and an O(n) path sum each: far too slow.
Recompute downward gains for every node:: Each ancestor re-walks its subtrees: O(n²) on a skewed tree. A post-order pass computes each gain once.
Assume the path goes through the root:: The best path may lie entirely in one subtree (for example a subtree with large values under a negative root).
Initialize best to 0:: If every value is negative the answer is the largest single (negative) node, and starting at 0 would wrongly report 0. Use −infinity (or the first node's value).

Four approaches, from naive to production

1 · beginner

Every node as the top, recompute gains

time O(n²)space O(h)

For each node, compute the best downward chain into each child with a helper (re-walking the subtree), add them to the node, and keep the best total. Visit all nodes this way.

int maxDown(TreeNode* node) {
    if (!node) return 0;
    return node->val + max({0, maxDown(node->left), maxDown(node->right)});
}

int maxPathSum(TreeNode* root) {
    int best = INT_MIN;
    function<void(TreeNode*)> visit = [&](TreeNode* node) {
        if (!node) return;
        int left = max(maxDown(node->left), 0);
        int right = max(maxDown(node->right), 0);
        best = max(best, node->val + left + right);
        visit(node->left);
        visit(node->right);
    };
    visit(root);
    return best;
}

public int maxPathSum(TreeNode root) {
    int[] best = {Integer.MIN_VALUE};
    visit(root, best);
    return best[0];
}

private void visit(TreeNode node, int[] best) {
    if (node == null) return;
    int left = Math.max(maxDown(node.left), 0);
    int right = Math.max(maxDown(node.right), 0);
    best[0] = Math.max(best[0], node.val + left + right);
    visit(node.left, best);
    visit(node.right, best);
}

private int maxDown(TreeNode node) {
    if (node == null) return 0;
    return node.val + Math.max(0, Math.max(maxDown(node.left), maxDown(node.right)));
}

def max_path_sum(root):
    best = float('-inf')
    def visit(node):
        nonlocal best
        if not node: return
        left = max(max_down(node.left), 0)
        right = max(max_down(node.right), 0)
        best = max(best, node.val + left + right)
        visit(node.left)
        visit(node.right)
    visit(root)
    return best

def max_down(node):
    if not node: return 0
    return node.val + max(0, max_down(node.left), max_down(node.right))

function maxPathSum(root: TreeNode | null): number {
  let best = -Infinity;
  const visit = (node: TreeNode | null): void => {
    if (!node) return;
    const left = Math.max(maxDown(node.left), 0);
    const right = Math.max(maxDown(node.right), 0);
    best = Math.max(best, node.val + left + right);
    visit(node.left);
    visit(node.right);
  };
  visit(root);
  return best;
}

function maxDown(node: TreeNode | null): number {
  if (!node) return 0;
  return node.val + Math.max(0, maxDown(node.left), maxDown(node.right));
}

Flaws & bottlenecks

Each ancestor recomputes the gains of everything below it: O(n²) on a skewed tree.
Two separate recursions (visit and maxDown) to keep in sync.
Uses a captured mutable best.

Interviewer cross-questions

Why is it quadratic?

Say: maxDown(child) walks the whole child subtree. A node at depth d is walked once for each of its d ancestors, so a chain of n nodes costs 1 + 2 + … + n = O(n²).

How do you avoid recomputing?

Say: Compute gains bottom-up once (post-order) and use them immediately: the gain of a node is derived from its children's gains, which are already known.

Why are negative gains clamped to 0?

Say: A path may stop at any node. If extending into a child makes the sum smaller, the best choice is to not extend, which contributes 0.

2 · intermediate

One post-order pass with a shared best

time O(n)space O(h)

A recursive gain(node) returns the best downward chain from that node, while also updating a shared best with the path that bends at the node (left gain + node + right gain).

int maxPathSum(TreeNode* root) {
    int best = INT_MIN;
    function<int(TreeNode*)> gain = [&](TreeNode* node) -> int {
        if (!node) return 0;
        int left = max(gain(node->left), 0);
        int right = max(gain(node->right), 0);
        best = max(best, node->val + left + right);
        return node->val + max(left, right);
    };
    gain(root);
    return best;
}

public int maxPathSum(TreeNode root) {
    int[] best = {Integer.MIN_VALUE};
    gain(root, best);
    return best[0];
}

private int gain(TreeNode node, int[] best) {
    if (node == null) return 0;
    int left = Math.max(gain(node.left, best), 0);
    int right = Math.max(gain(node.right, best), 0);
    best[0] = Math.max(best[0], node.val + left + right);
    return node.val + Math.max(left, right);
}

def max_path_sum(root):
    best = float('-inf')
    def gain(node):
        nonlocal best
        if not node: return 0
        left = max(gain(node.left), 0)
        right = max(gain(node.right), 0)
        best = max(best, node.val + left + right)
        return node.val + max(left, right)
    gain(root)
    return best

function maxPathSum(root: TreeNode | null): number {
  let best = -Infinity;
  const gain = (node: TreeNode | null): number => {
    if (!node) return 0;
    const left = Math.max(gain(node.left), 0);
    const right = Math.max(gain(node.right), 0);
    best = Math.max(best, node.val + left + right);
    return node.val + Math.max(left, right);
  };
  gain(root);
  return best;
}

Flaws & bottlenecks

Mutates a captured variable, which makes the function harder to reason about and unsafe to run in parallel.
Recursion depth equals the tree height.
The function plays two roles at once (returns the gain, records the answer as a side effect).

Interviewer cross-questions

Why is the value returned to the parent different from the value added to best?

Say: best may use BOTH children (the path bends at this node), but a path that continues up to the parent can use only ONE child, otherwise the path would fork. So we return node + max(left, right) but record node + left + right.

What if all values are negative?

Say: The answer is the single largest node. With best initialized to −infinity and the clamping of gains to 0, each node still records at least its own value.

What is the complexity?

Say: O(n) time (each node is processed once with O(1) work) and O(h) space for the recursion.

3 · advanced

Pure recursion returning a pair

time O(n)space O(h)

Return (best path inside the subtree, best downward gain from its root) from each call, and combine the two children's pairs. No captured variable is needed.

int maxPathSum(TreeNode* root) {
    function<pair<int, int>(TreeNode*)> go = [&](TreeNode* node) -> pair<int, int> {
        if (!node) return {INT_MIN, 0};
        auto [lb, lg] = go(node->left);
        auto [rb, rg] = go(node->right);
        int through = node->val + max(lg, 0) + max(rg, 0);
        return {max({lb, rb, through}), node->val + max({lg, rg, 0})};
    };
    return go(root).first;
}

public int maxPathSum(TreeNode root) {
    return go(root)[0];
}

private int[] go(TreeNode node) {
    if (node == null) return new int[]{Integer.MIN_VALUE, 0};
    int[] l = go(node.left); int lb = l[0], lg = l[1];
    int[] r = go(node.right); int rb = r[0], rg = r[1];
    int through = node.val + Math.max(lg, 0) + Math.max(rg, 0);
    return new int[]{Math.max(Math.max(lb, rb), through), node.val + Math.max(Math.max(lg, rg), 0)};
}

def max_path_sum(root):
    def go(node):
        if not node: return float('-inf'), 0
        lb, lg = go(node.left)
        rb, rg = go(node.right)
        through = node.val + max(lg, 0) + max(rg, 0)
        return max(lb, rb, through), node.val + max(lg, rg, 0)
    return go(root)[0]

function maxPathSum(root: TreeNode | null): number {
  const go = (node: TreeNode | null): [number, number] => {
    if (!node) return [-Infinity, 0];
    const [lb, lg] = go(node.left);
    const [rb, rg] = go(node.right);
    const through = node.val + Math.max(lg, 0) + Math.max(rg, 0);
    return [Math.max(lb, rb, through), node.val + Math.max(lg, rg, 0)];
  };
  return go(root)[0];
}

Flaws & bottlenecks

Allocates a pair (tuple) at every node.
The first component uses −infinity for an empty subtree, which must be handled carefully with unsigned or fixed-width types.
The combination formulas are easy to mix up (which gain feeds which value).

Interviewer cross-questions

What is the advantage over the shared-variable version?

Say: The function is pure: its result depends only on its input, so it is easier to test, reason about, and run in parallel. The whole answer travels up through return values.

Why does an empty subtree return −infinity for the "inside" value?

Say: There is no path inside it, so it must never win a max(). Returning 0 would let an empty subtree beat an all-negative real path.

Which is faster?

Say: Both are O(n). The pair version allocates a small array per node, so it is a bit slower in languages where that allocates; in languages with value-type tuples it is free.

4 · expert

Iterative post-order with a gain table

time O(n)space O(n)

Simulate the post-order traversal with an explicit stack and a "last visited" pointer, storing each finished node's gain in a table that its parent reads. No recursion, so depth is not limited by the call stack.

int maxPathSum(TreeNode* root) {
    if (!root) return 0;
    int best = INT_MIN;
    unordered_map<TreeNode*, int> gain;
    auto g = [&](TreeNode* n) { return n ? max(gain[n], 0) : 0; };
    vector<TreeNode*> stack;
    TreeNode* node = root;
    TreeNode* last = nullptr;
    while (node || !stack.empty()) {
        while (node) {
            stack.push_back(node);
            node = node->left;
        }
        TreeNode* top = stack.back();
        if (top->right && top->right != last) {
            node = top->right;
        } else {
            stack.pop_back();
            int left = g(top->left);
            int right = g(top->right);
            best = max(best, top->val + left + right);
            gain[top] = top->val + max(left, right);
            last = top;
        }
    }
    return best;
}

public int maxPathSum(TreeNode root) {
    if (root == null) return 0;
    int best = Integer.MIN_VALUE;
    Map<TreeNode, Integer> gain = new HashMap<>();
    java.util.function.Function<TreeNode, Integer> g = n -> n == null ? 0 : Math.max(gain.get(n), 0);
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;
    TreeNode last = null;
    while (node != null || !stack.isEmpty()) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        TreeNode top = stack.peek();
        if (top.right != null && top.right != last) {
            node = top.right;
        } else {
            stack.pop();
            int left = g.apply(top.left);
            int right = g.apply(top.right);
            best = Math.max(best, top.val + left + right);
            gain.put(top, top.val + Math.max(left, right));
            last = top;
        }
    }
    return best;
}

def max_path_sum(root):
    if not root: return 0
    best = float('-inf')
    gain = {}
    g = lambda n: max(gain[n], 0) if n else 0
    stack = []
    node = root
    last = None
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        top = stack[-1]
        if top.right and top.right is not last:
            node = top.right
        else:
            stack.pop()
            left = g(top.left)
            right = g(top.right)
            best = max(best, top.val + left + right)
            gain[top] = top.val + max(left, right)
            last = top
    return best

function maxPathSum(root: TreeNode | null): number {
  if (!root) return 0;
  let best = -Infinity;
  const gain = new Map<TreeNode, number>();
  const g = (n: TreeNode | null): number => (n ? Math.max(gain.get(n)!, 0) : 0);
  const stack: TreeNode[] = [];
  let node: TreeNode | null = root;
  let last: TreeNode | null = null;
  while (node || stack.length > 0) {
    while (node) {
      stack.push(node);
      node = node.left;
    }
    const top = stack[stack.length - 1];
    if (top.right && top.right !== last) {
      node = top.right;
    } else {
      stack.pop();
      const left = g(top.left);
      const right = g(top.right);
      best = Math.max(best, top.val + left + right);
      gain.set(top, top.val + Math.max(left, right));
      last = top;
    }
  }
  return best;
}

Flaws & bottlenecks

More code and subtler control flow (the "last visited" test) than recursion.
Needs a table (or stored field) holding a gain for every node: O(n) extra memory.
Easy to get the order wrong: a node may be processed only when BOTH children are done.

Interviewer cross-questions

Why do we need the last pointer?

Say: After exploring the left subtree we return to the top node without knowing if its right subtree has been done. If top.right equals last, we just came back from it, so the node can be processed; otherwise the right subtree must be explored first.

Why is it worth the complexity?

Say: A skewed tree of 100,000 nodes would overflow a recursive call stack in most runtimes. The explicit stack lives on the heap, so only memory limits it.

Could you drop the table?

Say: You can store the gain directly in a field of the node (if you may modify it), or keep gains on a parallel stack aligned with the traversal. The table is the simplest version.

Synchronized code walkthrough

Showing: Every node as the top, recompute gains — shares the player above; click any step to jump.

int maxDown(TreeNode* node) {
    if (!node) return 0;
    return node->val + max({0, maxDown(node->left), maxDown(node->right)});
}

int maxPathSum(TreeNode* root) {
    int best = INT_MIN;
    function<void(TreeNode*)> visit = [&](TreeNode* node) {
        if (!node) return;
        int left = max(maxDown(node->left), 0);
        int right = max(maxDown(node->right), 0);
        best = max(best, node->val + left + right);
        visit(node->left);
        visit(node->right);
    };
    visit(root);
    return best;
}

public int maxPathSum(TreeNode root) {
    int[] best = {Integer.MIN_VALUE};
    visit(root, best);
    return best[0];
}

private void visit(TreeNode node, int[] best) {
    if (node == null) return;
    int left = Math.max(maxDown(node.left), 0);
    int right = Math.max(maxDown(node.right), 0);
    best[0] = Math.max(best[0], node.val + left + right);
    visit(node.left, best);
    visit(node.right, best);
}

private int maxDown(TreeNode node) {
    if (node == null) return 0;
    return node.val + Math.max(0, Math.max(maxDown(node.left), maxDown(node.right)));
}

def max_path_sum(root):
    best = float('-inf')
    def visit(node):
        nonlocal best
        if not node: return
        left = max(max_down(node.left), 0)
        right = max(max_down(node.right), 0)
        best = max(best, node.val + left + right)
        visit(node.left)
        visit(node.right)
    visit(root)
    return best

def max_down(node):
    if not node: return 0
    return node.val + max(0, max_down(node.left), max_down(node.right))

function maxPathSum(root: TreeNode | null): number {
  let best = -Infinity;
  const visit = (node: TreeNode | null): void => {
    if (!node) return;
    const left = Math.max(maxDown(node.left), 0);
    const right = Math.max(maxDown(node.right), 0);
    best = Math.max(best, node.val + left + right);
    visit(node.left);
    visit(node.right);
  };
  visit(root);
  return best;
}

function maxDown(node: TreeNode | null): number {
  if (!node) return 0;
  return node.val + Math.max(0, maxDown(node.left), maxDown(node.right));
}

int maxPathSum(TreeNode* root) {
    int best = INT_MIN;
    function<int(TreeNode*)> gain = [&](TreeNode* node) -> int {
        if (!node) return 0;
        int left = max(gain(node->left), 0);
        int right = max(gain(node->right), 0);
        best = max(best, node->val + left + right);
        return node->val + max(left, right);
    };
    gain(root);
    return best;
}

public int maxPathSum(TreeNode root) {
    int[] best = {Integer.MIN_VALUE};
    gain(root, best);
    return best[0];
}

private int gain(TreeNode node, int[] best) {
    if (node == null) return 0;
    int left = Math.max(gain(node.left, best), 0);
    int right = Math.max(gain(node.right, best), 0);
    best[0] = Math.max(best[0], node.val + left + right);
    return node.val + Math.max(left, right);
}

def max_path_sum(root):
    best = float('-inf')
    def gain(node):
        nonlocal best
        if not node: return 0
        left = max(gain(node.left), 0)
        right = max(gain(node.right), 0)
        best = max(best, node.val + left + right)
        return node.val + max(left, right)
    gain(root)
    return best

function maxPathSum(root: TreeNode | null): number {
  let best = -Infinity;
  const gain = (node: TreeNode | null): number => {
    if (!node) return 0;
    const left = Math.max(gain(node.left), 0);
    const right = Math.max(gain(node.right), 0);
    best = Math.max(best, node.val + left + right);
    return node.val + Math.max(left, right);
  };
  gain(root);
  return best;
}

int maxPathSum(TreeNode* root) {
    function<pair<int, int>(TreeNode*)> go = [&](TreeNode* node) -> pair<int, int> {
        if (!node) return {INT_MIN, 0};
        auto [lb, lg] = go(node->left);
        auto [rb, rg] = go(node->right);
        int through = node->val + max(lg, 0) + max(rg, 0);
        return {max({lb, rb, through}), node->val + max({lg, rg, 0})};
    };
    return go(root).first;
}

public int maxPathSum(TreeNode root) {
    return go(root)[0];
}

private int[] go(TreeNode node) {
    if (node == null) return new int[]{Integer.MIN_VALUE, 0};
    int[] l = go(node.left); int lb = l[0], lg = l[1];
    int[] r = go(node.right); int rb = r[0], rg = r[1];
    int through = node.val + Math.max(lg, 0) + Math.max(rg, 0);
    return new int[]{Math.max(Math.max(lb, rb), through), node.val + Math.max(Math.max(lg, rg), 0)};
}

def max_path_sum(root):
    def go(node):
        if not node: return float('-inf'), 0
        lb, lg = go(node.left)
        rb, rg = go(node.right)
        through = node.val + max(lg, 0) + max(rg, 0)
        return max(lb, rb, through), node.val + max(lg, rg, 0)
    return go(root)[0]

function maxPathSum(root: TreeNode | null): number {
  const go = (node: TreeNode | null): [number, number] => {
    if (!node) return [-Infinity, 0];
    const [lb, lg] = go(node.left);
    const [rb, rg] = go(node.right);
    const through = node.val + Math.max(lg, 0) + Math.max(rg, 0);
    return [Math.max(lb, rb, through), node.val + Math.max(lg, rg, 0)];
  };
  return go(root)[0];
}

int maxPathSum(TreeNode* root) {
    if (!root) return 0;
    int best = INT_MIN;
    unordered_map<TreeNode*, int> gain;
    auto g = [&](TreeNode* n) { return n ? max(gain[n], 0) : 0; };
    vector<TreeNode*> stack;
    TreeNode* node = root;
    TreeNode* last = nullptr;
    while (node || !stack.empty()) {
        while (node) {
            stack.push_back(node);
            node = node->left;
        }
        TreeNode* top = stack.back();
        if (top->right && top->right != last) {
            node = top->right;
        } else {
            stack.pop_back();
            int left = g(top->left);
            int right = g(top->right);
            best = max(best, top->val + left + right);
            gain[top] = top->val + max(left, right);
            last = top;
        }
    }
    return best;
}

public int maxPathSum(TreeNode root) {
    if (root == null) return 0;
    int best = Integer.MIN_VALUE;
    Map<TreeNode, Integer> gain = new HashMap<>();
    java.util.function.Function<TreeNode, Integer> g = n -> n == null ? 0 : Math.max(gain.get(n), 0);
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;
    TreeNode last = null;
    while (node != null || !stack.isEmpty()) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        TreeNode top = stack.peek();
        if (top.right != null && top.right != last) {
            node = top.right;
        } else {
            stack.pop();
            int left = g.apply(top.left);
            int right = g.apply(top.right);
            best = Math.max(best, top.val + left + right);
            gain.put(top, top.val + Math.max(left, right));
            last = top;
        }
    }
    return best;
}

def max_path_sum(root):
    if not root: return 0
    best = float('-inf')
    gain = {}
    g = lambda n: max(gain[n], 0) if n else 0
    stack = []
    node = root
    last = None
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        top = stack[-1]
        if top.right and top.right is not last:
            node = top.right
        else:
            stack.pop()
            left = g(top.left)
            right = g(top.right)
            best = max(best, top.val + left + right)
            gain[top] = top.val + max(left, right)
            last = top
    return best

function maxPathSum(root: TreeNode | null): number {
  if (!root) return 0;
  let best = -Infinity;
  const gain = new Map<TreeNode, number>();
  const g = (n: TreeNode | null): number => (n ? Math.max(gain.get(n)!, 0) : 0);
  const stack: TreeNode[] = [];
  let node: TreeNode | null = root;
  let last: TreeNode | null = null;
  while (node || stack.length > 0) {
    while (node) {
      stack.push(node);
      node = node.left;
    }
    const top = stack[stack.length - 1];
    if (top.right && top.right !== last) {
      node = top.right;
    } else {
      stack.pop();
      const left = g(top.left);
      const right = g(top.right);
      best = Math.max(best, top.val + left + right);
      gain.set(top, top.val + Math.max(left, right));
      last = top;
    }
  }
  return best;
}