Frontend School

Max Stable Path Sum in a Binary Tree

DSA
hard

Max Stable Path Sum in a Binary Tree

Hard
Tree
DFS
Recursion
Binary Tree

Overview

In Urban Company's service ecosystem, hierarchical data structures often represent dependencies, service categories, or operational workflows. Ensuring 'stability' in these hierarchies is crucial for reliable service delivery and resource allocation. This problem challenges you to identify and quantify the most valuable 'stable' pathways within such a system, modeled as a binary tree.

What you need to do / Task

Given the root of a binary tree and an integer K, find the maximum sum of node values along any "stable" path from the root to a leaf node. A path is considered "stable" if the absolute difference between the values of any two adjacent nodes (parent and child) along that path is less than or equal to K.

Your task is to implement the maxStablePathSum function that returns this maximum sum. If no stable path exists from the root to any leaf, return -1.

Input & output

Input:

  • root: The root node of a binary tree. Each TreeNode has an integer val, a left child, and a right child.
  • K: An integer representing the maximum allowed absolute difference between adjacent nodes for a path to be stable.

Output:

  • An integer representing the maximum sum of node values found among all stable paths from the root to a leaf. Return -1 if no such path exists.

Clarifications

  • A path from the root to a single-node tree (where the root is also a leaf) is considered stable, as there are no adjacent node pairs to violate the condition.
  • Node values can be negative, zero, or positive.
  • K will always be non-negative.

Examples

1

Example 1

Input:

root = [10,5,15,3,7,null,18], K = 5

Output:

43

Note:

The stable paths from root to leaf are:

  1. 10 -> 5 -> 3 (Differences: |10-5|=5, |5-3|=2. Both <= K=5). Sum = 10+5+3 = 18.
  2. 10 -> 5 -> 7 (Differences: |10-5|=5, |5-7|=2. Both <= K=5). Sum = 10+5+7 = 22.
  3. 10 -> 15 -> 18 (Differences: |10-15|=5, |15-18|=3. Both <= K=5). Sum = 10+15+18 = 43. The maximum sum is 43.
2

Example 2

Input:

root = [10,1,20], K = 5

Output:

-1

Note:

Paths from root to leaf:

  1. 10 -> 1 (Difference: |10-1|=9. 9 > K=5). Not a stable path.
  2. 10 -> 20 (Difference: |10-20|=10. 10 > K=5). Not a stable path. Since no stable paths exist, return -1.
3

Example 3

Input:

root = [100], K = 0

Output:

100

Note:

The tree has a single node. This path is stable by definition (no adjacent nodes to violate the condition). The sum is 100.

Constraints

Constraints & assumptions

  • The number of nodes in the tree N is between 1 and 10^5 (inclusive).
  • Node values (TreeNode.val) are between -10^9 and 10^9 (inclusive).
  • K is between 0 and 10^9 (inclusive).
  • The input root will always be a valid TreeNode (i.e., not null).

What interviewers evaluate

  • Correctness in identifying stable paths from root to leaf.
  • Efficiency of the algorithm in terms of time and space complexity.
  • Proper handling of edge cases, such as a single-node tree or no stable paths.
  • Clarity and structure of the code, demonstrating good problem-solving and coding practices.

Loading editor...