Neural Mastery
← Practice
Binary Tree Maximum Path Sumhard

Binary Tree Maximum Path Sum

hard Coding Interview Patterns 25–30 min

NumPy allowed · plain Python earns 10 bonus points

Interactive
Graph & Tree Traversal, Step by Step
Structure
Algorithm
ABCDE
visiting A -> visited order so far: [A]
queue now: [B, C]
Step 1 / 5
Both modes run the real algorithm from the linked practice problem, one step at a time -- edit the graph or pick different tree nodes and every step recomputes live.

Implement Binary Tree Maximum Path Sum -- one of the most-cited "hard" tree problems, requiring you to track two DIFFERENT quantities at each node: the best path usable by an ancestor (one-sided) vs. the best path THROUGH this node (both sides, only valid as a final answer here).

Related Skills

Task

Implement max_path_sum(root): for each node, compute the best "downward" gain from each child (clamped to 0, since a negative-sum branch should just be excluded rather than dragging the total down), use both children's gains together to update a global best (a path bending through this node), but RETURN to the caller only this node's value plus the better of its two one-sided child gains (since a path continuing upward through an ancestor can only use one branch, not both).

Function Signature

max_path_sum(root: dict) -> int

Examples

Example 1: Small All-Positive Tree
Input: root = {'val': 1, 'left': {'val': 2, 'left': None, 'right': None}, 'right': {'val': 3, 'left': None, 'right': None}}
Output: 6
Explanation: Path 2 -> 1 -> 3
Example 2: Negative Root, Path Excludes It
Input: root = {'val': -10, 'left': {'val': 9, 'left': None, 'right': None}, 'right': {'val': 20, 'left': {'val': 15, 'left': None, 'right': None}, 'right': {'val': 7, 'left': None, 'right': None}}}
Output: 42
Explanation: Path 15 -> 20 -> 7, entirely avoiding the negative root

Constraints

  • Libraries are allowed; a plain-Python solution earns 10 bonus points.
  • A path does not need to pass through the root, and does not need to end at a leaf -- any two nodes (or a single node) qualify.
  • Node values may be negative -- clamp a child's contribution to 0 rather than including a net-negative branch.
  • The tree is never empty for this problem.
Python3Saved ✓
def max_path_sum(root: dict) -> int:
"""root: a non-empty tree node as {'val', 'left', 'right'}. A path
is any sequence of nodes connected by edges, and does NOT need to
pass through the root or end at a leaf -- it may start and end at
any two nodes (or be a single node). Return the maximum possible
sum of node values along any such path. Node values may be
negative."""
# Your implementation here
pass

Case 1: Small All-Positive Tree
Input: root = {'val': 1, 'left': {'val': 2, 'left': None, 'right': None}, 'right': {'val': 3, 'left': None, 'right': None}}
Expected: 6
Case 2: Negative Root, Path Excludes It
Input: root = {'val': -10, 'left': {'val': 9, 'left': None, 'right': None}, 'right': {'val': 20, 'left': {'val': 15, 'left': None, 'right': None}, 'right': {'val': 7, 'left': None, 'right': None}}}
Expected: 42