Maximum path sum in a tree: A Sample Coding Interview Solution

The coding question

Given a binary tree of integers, return the largest sum of any path. Follow-up: each node has an active flag. Return the largest sum of a path that starts and ends at active nodes.

Ask a few questions first

Ask	What we'll assume
Can values be negative?	Yes. That's what makes it interesting.
Does a path need at least one node?	Yes. So if every value is negative, the answer is the biggest single value.
Can a path go up and then down?	Yes, it can bend once at a node, using its left side and right side. It can't use a node twice.
Can the tree be empty?	We'll assume there's at least one node.
Follow-up: can the path be a single active node?	Yes, it starts and ends at the same node. The nodes in between don't have to be active.
Follow-up: what if no node is active?	Return None.

A couple of examples

Input	Output
1, with children 2 and 3	6 (2 → 1 → 3)
-10, with children 9 and 20. 20 has children 15 and 7	42 (15 → 20 → 7)
A single node, -3	-3
5 (active), with children 4 and -1. 4 has a left child -2 (active). -1 has a right child 8 (active)	Any path: 16 (4 → 5 → -1 → 8). Active ends: 14 (-2 → 4 → 5 → -1 → 8)
10, with children -5 (active) and 20	Any path: 30 (10 → 20). Active ends: -5 (just the -5 node)

Start with brute force

Every path is between two nodes. Try every pair of nodes, find the path between them, and add it up. Keep the biggest. For the follow-up, only try pairs where both nodes are active.

Cost: There are about n² pairs and each path can be n long, so O(n³) time. Even at a few thousand nodes that's way too slow.

A better way

Look at the highest node on any path. The path comes up from its left side, goes through it, and goes down its right side. Either side can be empty.

So at each node, you want two different numbers. To record as a possible answer: the node plus the best downward path on the left plus the best downward path on the right. To return to its parent: the node plus only the better of its two sides, because the parent's path can't fork.

A side that adds up to a negative number only hurts, so treat it as 0. That's skipping it. One pass after the children, a post-order walk of the tree, gets everything. It's a small kind of dynamic programming: each node's answer is built from its children's.

The follow-up changes what a side means. A downward path now has to end at an active node, so you can't skip a side by treating it as 0 any more, unless the current node is active and can be the end itself. Return None when a subtree has no active node, and only build sums from sides that exist.

Keep a best-so-far, starting at the root's value.
Write a helper that returns the best downward path starting at a node. For an empty child it returns 0.
In the helper, get the left and right results, and turn any negative one into 0.
Update best-so-far with node + left + right. That's the path bending here.
Return node + the bigger of left and right.
Follow-up: the helper returns the best downward path that ends at an active node, or None. The ways to end are the node alone (if it's active), node + left, and node + right.
Follow-up: if the node is active, any of those ends is a full path with this node as the other end. If both sides exist, node + left + right bends here. Record the best of these.

The code

solution.pypython

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


def max_path_sum(root):
    best = root.val

    def gain(node):
        # The best sum of a path that starts here and goes down one side.
        nonlocal best
        if node is None:
            return 0
        left = max(gain(node.left), 0)
        right = max(gain(node.right), 0)
        # A path that bends here uses both sides.
        best = max(best, node.val + left + right)
        return node.val + max(left, right)

    gain(root)
    return best


def max_active_path_sum(root):
    # Both ends of the path must be active. None if no node is active.
    best = None

    def down(node):
        # The best sum of a path that starts here, goes down,
        # and ends at an active node. None if there isn't one.
        nonlocal best
        if node is None:
            return None
        left = down(node.left)
        right = down(node.right)
        ends = []  # best ways to finish a downward path from here
        if node.active:
            ends.append(node.val)
        if left is not None:
            ends.append(node.val + left)
        if right is not None:
            ends.append(node.val + right)
        candidates = []
        if node.active:
            candidates.extend(ends)  # this node is one end
        if left is not None and right is not None:
            candidates.append(node.val + left + right)  # bends here
        for total in candidates:
            if best is None or total > best:
                best = total
        return max(ends) if ends else None

    down(root)
    return best

	Cost	Why
Time	O(n)	Each node is visited once and does a fixed amount of work, in both versions
Space	O(h)	The recursion goes as deep as the tree's height h. That's n for a tree that's one long line

Test it

Walk through one of the examples out loud, then check the cases that tend to break things:

One node. The answer is its value, even if it's negative.
Every value negative, like -2 with a child -1. The answer is -1, a single node. Starting best at 0 would wrongly give 0.
A positive node with only negative children, like 2 with children -1 and -2. Skip both sides and the answer is 2.
Follow-up: no active nodes. Return None.
Follow-up: one active node with big positive neighbors that aren't active, like the last example. The answer is just that node, even though it's negative.
A tree that's one long line. Check that the recursion doesn't go too deep in Python for big inputs.

Common mistakes

Returning node + left + right to the parent. A parent can't use a path that already forks, so that over-counts.
Starting best at 0 instead of the root's value. All-negative trees then return 0, which isn't a real path.
Not dropping negative sides in the first version. Adding a negative branch just makes the sum smaller.
Reusing the 'treat negative as 0' trick in the follow-up. That quietly ends a path at a node that isn't active.
Using a plain variable for best inside the helper without nonlocal, or a global that isn't reset between test cases.

Follow-up questions

How would you return the path itself as well as the sum?

Have the helper also return the list of nodes for its best downward path. When you update best, save the left path reversed, the node, and the right path.

What if the tree's a million nodes deep?

Python's recursion limit will blow up. Do a post-order walk with your own stack, and store each node's downward result in a dictionary.

What if the path must have at least two different active nodes?

Track the best downward path that ends at an active node strictly below the current one, separately from the one that ends at the node itself. Then only record sums that join two different ends.

How the time adds up

Minutes	What you're doing
0–5	Ask questions, especially about negative values
5–10	Brute force: try every pair of nodes
10–20	Work out what each node records and what it returns
20–35	Write the code, then change it for active nodes
35–40	Test it, including an all-negative tree and no active nodes
40–45	Follow-up questions

Key concepts used here

We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by DoorDash.