Skip to content

Most Valuable Trail

Jump to bottom
Andrew Burke edited this page Aug 19, 2026 · 1 revision

TIP103 Unit 12 Session 1 (Click for link to problem statements)

Most Valuable Trail

A binary tree of trail markers has an integer value on each node (values may be negative). A path is any sequence of connected nodes, and it may start and end anywhere, but it uses each node at most once and does not split.

Given the root, return the maximum possible sum of the values along any path.

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

def max_path_sum(root):
    pass

Problem Highlights

  • 💡 Difficulty: Hard
  • ⏰ Time to complete: 30-40 mins
  • 🛠️ Topics: Binary Trees, Depth-First Search (DFS), Recursion, Global Maximum Tracking

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?

  • Q: Does the path have to pass through the root?

    • A: No. A path may start and end at any nodes in the tree, as long as the nodes form a connected, non-splitting chain.

  • Q: Can a path "split" — that is, include a node together with both of its children and then keep extending on both sides?

    • A: A path may bend through a node (left subtree → node → right subtree), but once it bends it cannot continue upward to that node's parent. Each node is used at most once and the path never branches into more than two directions.

  • Q: What if every value in the tree is negative — can the path be empty?

    • A: No, a path must contain at least one node. With all-negative values, the answer is the single node with the largest (least negative) value.
HAPPY CASE
Input: root = TreeNode(-10, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
       -10
       /  \
      9    20
          /  \
         15   7
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with sum 15 + 20 + 7 = 42. Note that the path does not pass through the root, and including -10 would only lower the total.

EDGE CASE
Input: root = TreeNode(-3)
Output: -3
Explanation: A path must contain at least one node, so with a single negative marker the best (and only) path is that node itself.

Input: root = TreeNode(-2, TreeNode(-1), TreeNode(-4))
Output: -1
Explanation: Every value is negative, so extending any path only decreases the sum. The best path is the single least-negative node, -1.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Binary Tree Path Problems, we can consider the following approaches:

  • DFS (Post-Order Traversal): Compute information about each subtree from the bottom up. At every node we need the best "downward" path sum coming out of each child before we can decide anything about the node itself.
  • Global Maximum Tracking: The value a recursive call returns (the best path that can be extended to the parent) is different from the answer we are looking for (the best path that may bend at a node). Track the overall best in a variable outside the recursion and update it at every node.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Do a post-order DFS. For each node, ask its children for their best downward gain — the maximum sum of a path that starts at the child and goes down into its subtree. Clamp negative gains to 0 (it is better to not include a losing branch at all). The best path that bends at this node is node.val + left_gain + right_gain; compare it against a global maximum. But the value returned to the parent can only continue in one direction, so return node.val + max(left_gain, right_gain).

1) Initialize a global variable max_sum to negative infinity.
2) Define a recursive helper max_gain(node):
   a) Base case: if node is None, return 0.
   b) left_gain  = max(max_gain(node.left), 0)   // ignore branches that lose value
   c) right_gain = max(max_gain(node.right), 0)
   d) Update max_sum with node.val + left_gain + right_gain
      // best path that bends (peaks) at this node
   e) Return node.val + max(left_gain, right_gain)
      // a path continuing up to the parent can only use one side
3) Call max_gain(root) and return max_sum.

⚠️ Common Mistakes

  • Returning node.val + left_gain + right_gain to the parent. A path that already bends through both children cannot extend upward — the return value may use at most one child.
  • Forgetting to clamp negative child gains to 0, which drags down otherwise-optimal paths.
  • Initializing max_sum to 0 instead of negative infinity, which returns the wrong answer for all-negative trees (a path must contain at least one node, so an "empty" path of sum 0 is not allowed).
  • Only considering paths that pass through the root.

4: I-mplement

Implement the code to solve the algorithm.

def max_path_sum(root):
    max_sum = float('-inf')

    def max_gain(node):
        nonlocal max_sum
        if node is None:
            return 0

        # Best downward gain from each child; ignore negative contributions
        left_gain = max(max_gain(node.left), 0)
        right_gain = max(max_gain(node.right), 0)

        # Best path that "peaks" (bends) at this node may use both children
        path_through_node = node.val + left_gain + right_gain
        max_sum = max(max_sum, path_through_node)

        # A path continuing up to the parent can only use one side
        return node.val + max(left_gain, right_gain)

    max_gain(root)
    return max_sum

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Input: root = TreeNode(-10, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))

    • max_gain(9) returns 9; max_sum becomes 9.
    • max_gain(15) returns 15 and max_gain(7) returns 7; max_sum becomes 15.
    • At node 20: path_through_node = 20 + 15 + 7 = 42, so max_sum becomes 42. The call returns 20 + max(15, 7) = 35.
    • At node -10: path_through_node = -10 + 9 + 35 = 34, which does not beat 42.
    • Output: 42

  • Input: root = TreeNode(-3)

    • Both child gains are clamped to 0, so max_sum = -3 + 0 + 0 = -3.
    • Output: -3 (negative infinity as the initial value lets a single negative node win.)

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of nodes in the tree and H is the height of the tree.

  • Time Complexity: O(N) because the DFS visits every node exactly once and does constant work per node.
  • Space Complexity: O(H) for the recursion stack — O(log N) for a balanced tree, O(N) in the worst case of a completely skewed tree.

Clone this wiki locally