Frontend School

Count Restricted Path Sums in Binary Tree

DSA
hard

Count Restricted Path Sums in Binary Tree

Hard
Recursion
Binary Tree
Depth-First Search
path finding

Overview

In a system monitoring network topology, we often analyze "paths" through connected components to understand data flow or resource dependencies. Sometimes, we're interested in paths that satisfy specific criteria, such as a cumulative value and a maximum hop count, to identify critical or bottleneck segments. This problem requires you to count such restricted paths in a hierarchical (tree-like) network representation.

What you need to do / Task

You are given the root of a binary tree, an integer targetSum, and an integer maxNodes. Your task is to implement a function countRestrictedPathSums that returns the total number of paths in the tree satisfying the following conditions:

  1. The sum of the node values along the path equals targetSum.
  2. The path contains at most maxNodes nodes (inclusive).
  3. A path must be downwards: it can start at any node and end at any descendant node (or the starting node itself). It does not need to pass through the root.

Input & output

countRestrictedPathSums function signature:

function countRestrictedPathSums(root: TreeNode | null, targetSum: number, maxNodes: number): number
  • root: The root node of a binary tree. Each TreeNode has an integer val, a left child, and a right child.
  • targetSum: An integer representing the required sum for a valid path.
  • maxNodes: An integer representing the maximum allowed number of nodes in a valid path.
  • Returns: An integer, the total count of paths that satisfy both the sum and node count restrictions.

Clarifications

  • An empty tree (root = null) should result in 0 paths.
  • A path consisting of a single node is valid if its value equals targetSum and maxNodes >= 1.
  • Node values can be positive, negative, or zero.
  • targetSum can be positive, negative, or zero.

Examples

1

Example 1

Input:

root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8, maxNodes = 3

Output:

3

Note:

The tree looks like this: 10 /
5 -3 / \
3 2 11 / \ \ 3 -2 1

Paths that sum to 8 with at most 3 nodes:

  1. 5 -> 3 (length 2, sum 8)
  2. 5 -> 2 -> 1 (length 3, sum 8)
  3. -3 -> 11 (length 2, sum 8)
2

Example 2

Input:

root = [1,2,3], targetSum = 3, maxNodes = 1

Output:

1

Note:

The tree looks like this: 1 /
2 3 Paths that sum to 3 with at most 1 node:

  1. 3 (length 1, sum 3) The path 1 -> 2 sums to 3, but has 2 nodes, exceeding maxNodes = 1.
3

Example 3

Input:

root = [1,2,3], targetSum = 6, maxNodes = 5

Output:

0

Note:

No path in the tree sums to 6.

Constraints

Constraints & assumptions

  • The number of nodes in the tree is between 0 and 2000.
  • Node.val is between -1000 and 1000.
  • targetSum is between -10^9 and 10^9.
  • maxNodes is between 1 and 2000.
  • The tree structure can be arbitrary (not necessarily balanced).

What interviewers evaluate

  • Correctness: The solution accurately identifies all restricted paths according to the problem statement.
  • Algorithm Design: Demonstrates a clear understanding of recursive tree traversal and effective state management for multiple path constraints.
  • Code Quality: Writes clean, readable, and well-structured code with appropriate variable names and function decomposition.
  • Efficiency: The solution is reasonably optimized for the given constraints, avoiding unnecessary computations.

Loading editor...