Maximum Root Leaf Path Sum — Problem Statement & Solution Guide

TreesMediumMixed

TimeO(N)

SpaceO(H)

Problem Description

You are given a rooted tree with N nodes numbered from 1 to N. Node 1 is the root. Each node i holds an integer value v[i]. The tree structure is supplied as N‑1 directed edges (parent child) that guarantee a single parent for every non‑root node. Your task is to compute the largest possible sum of node values encountered along any path that starts at the root and ends at a leaf (a node with no children). Return this maximum sum as a single integer.

Input format:

- The first line contains an integer N, the number of nodes.

- The second line contains N space‑separated integers v[1] … v[N].

- Each of the next N‑1 lines contains two integers p and c, denoting a directed edge from parent p to child c.

Output format:

- A single integer representing the maximum root‑to‑leaf path sum.

The tree may contain negative values, and the answer can be negative if all possible sums are negative.

DSA Pattern Breakdown

"Maximum Root Leaf Path Sum"

medium

WHY DOES IT MATTER?

Root‑to‑leaf path problems are a classic example of tree DP where local decisions (choosing a child) propagate to a global optimum. Mastering this pattern teaches you how to convert recursive definitions into efficient traversals, a skill that recurs in many graph and tree challenges.

OPTIMIZATION CHALLENGE

The key insight is to avoid recomputing path sums for overlapping sub‑paths. By carrying the cumulative sum forward during a single DFS, each edge contributes to the total exactly once, collapsing an exponential enumeration into linear work.

REAL-WORLD CONNECTION

Think of a hierarchical organization where each manager adds a cost or profit to a project. The maximum root‑to‑leaf sum mirrors finding the most profitable chain of command from the CEO down to an operational team, a scenario common in financial risk modeling and supply‑chain optimization.

During an interview, write a clean recursive DFS that returns the maximum sum from the current node to any leaf in its subtree; then combine it with the node's own value. This functional style often leads to fewer bugs than managing a global variable.

COMPLEXITY AT A GLANCE

⏱ Time:O(N)

💾 Space:O(H)

Core Theory — Why This Approach?

The problem reduces to finding the maximum sum of values along any root‑to‑leaf path in a rooted tree. A naive solution would enumerate every leaf, compute the sum of values on the path from the root to that leaf, and keep the maximum; however, this requires O(N^2) time in the worst case because each path may be recomputed from scratch. The optimal paradigm leverages depth‑first search (DFS) or breadth‑first search (BFS) with dynamic programming: as we traverse the tree, we maintain the cumulative sum from the root to the current node. When we reach a leaf, the stored sum is a candidate for the answer, and the global maximum is updated. This single pass visits each node exactly once, yielding linear time. The recursion stack (or an explicit stack for iterative DFS) holds at most the height of the tree, giving O(H) auxiliary space, which is O(N) in the worst case but optimal for a tree traversal.

Interview Questions on This Problem

Q1How would you modify the solution if each node could have a negative value and you were asked for the maximum root‑to‑leaf sum?

The same DFS approach works unchanged because the cumulative sum naturally incorporates negative contributions; we simply keep the global maximum across all leaf nodes. No extra handling is needed beyond initializing the answer to negative infinity.

Q2Can you compute the maximum root‑to‑leaf sum in a tree stored as an adjacency list without explicit parent pointers?

Yes. Perform a DFS starting from node 1 (the root) while passing the parent node as a parameter to avoid revisiting it. Accumulate the sum along the recursion and update the answer when a node has no children other than its parent (i.e., it is a leaf).

Q3What is the time and space complexity if the tree is extremely unbalanced (like a linked list) and you implement the DFS recursively?

The time remains O(N) because each node is visited once. The recursion depth becomes O(N) for a degenerate tree, so the call stack uses O(N) space, which may cause a stack overflow in languages with limited recursion depth; an iterative stack can mitigate this.

Examples

Example 1

Input

5
10 -2 7 8 3
1 2
1 3
2 4
2 5

Output

Explanation: Root‑to‑leaf paths are: 1→2→4: 10 + (-2) + 8 = 16 1→2→5: 10 + (-2) + 3 = 11 1→3: 10 + 7 = 17 The greatest sum is 17.

Example 2

Input

4
-5 -1 -2 -3
1 2
1 3
3 4

Output

-6

Explanation: Root‑to‑leaf paths are: 1→2: -5 + (-1) = -6 1→3→4: -5 + (-2) + (-3) = -10 The maximum among the negative sums is -6.

Example 3

Input

7
5 4 6 1 2 9 3
1 2
1 3
2 4
2 5
3 6
3 7

Output

Explanation: Root‑to‑leaf paths are: 1→2→4: 5 + 4 + 1 = 10 1→2→5: 5 + 4 + 2 = 11 1→3→6: 5 + 6 + 9 = 20 1→3→7: 5 + 6 + 3 = 14 The largest sum is 20.

Constraints

1 <= N <= 2*10^5
-10^9 <= v[i] <= 10^9
The given edges form a valid rooted tree with node 1 as the root.

Optimal Approach & Strategy

Perform a single DFS from the root, propagate the cumulative sum, and update the answer at each leaf; this visits each node only once.

Brute Force Approach

Enumerate every leaf, for each leaf climb back to the root summing node values, and keep the maximum; this repeats work for shared ancestors.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(N)

function maxRootLeafSum(root) {
      if (!root) return -Infinity;
      if (!root.children || root.children.length === 0) return root.value;
      let maxSum = -Infinity;
      for (let child of root.children) {
         maxSum = Math.max(maxSum, maxRootLeafSum(child));
      }
      return root.value + maxSum;
   }

class Solution {
   public:
      int maxRootLeafSum(TreeNode* root) {
         if (!root) return INT_MIN;
         if (!root->children || root->children.size() == 0) return root->val;
         int maxSum = INT_MIN;
         for (TreeNode* child : root->children) {
            maxSum = std::max(maxSum, maxRootLeafSum(child));
         }
         return root->val + maxSum;
      }
   };

class Solution {
      public int maxRootLeafSum(TreeNode root) {
         if (root == null) return Integer.MIN_VALUE;
         if (root.children == null || root.children.size() == 0) return root.val;
         int maxSum = Integer.MIN_VALUE;
         for (TreeNode child : root.children) {
            maxSum = Math.max(maxSum, maxRootLeafSum(child));
         }
         return root.val + maxSum;
      }
   }

def max_root_leaf_sum(root):
      if not root:
         return float('-inf')
      if not root.children or len(root.children) == 0:
         return root.value
      max_sum = float('-inf')
      for child in root.children:
         max_sum = max(max_sum, max_root_leaf_sum(child))
      return root.value + max_sum

function maxRootLeafSum(root) {
      if (!root) return -Infinity;
      if (!root.children || root.children.length === 0) return root.value;
      let maxSum = -Infinity;
      for (let child of root.children) {
         maxSum = Math.max(maxSum, maxRootLeafSum(child));
      }
      return root.value + maxSum;
   }

Asked in Top Tech Interviews

tree-data-structuresmediumrecursion

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Maximum Root Leaf Path Sum Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Trees

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Maximum Root Leaf Path Sum — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor