Grokking Tree Coding Patterns for Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Path Sum III (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given the root of a binary tree and an integer targetSum, return the count of number of paths in the tree where the sum of the values along the path equals targetSum.

A path can start and end at any node, but it must go downward, meaning it can only travel from parent nodes to child nodes.`

Examples

Example 1:

  • Input: targetSum = 10, root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
      1
     / \
    2   3
   / \ / \
  4  5 6  7
 / \ /
8  9 10
  • Expected Output: 3
  • Justification: The paths that sum to 10 are:
    • 1 → 3 → 6
    • 3 → 7
    • 10

Example 2:

  • Input: targetSum = 12, root = [5, 4, 6, 3, null, 7, 8, null, null, 2, 1]
    5
   / \
  4   6
 /   / \
3   7   8
   / \      
   2  1
  • Expected Output: 1
  • Justification: The paths that sum to 12 are:
    • 5 → 4 → 3

Example 3:

  • Input: targetSum = 18, root = [10, 5, -3, 3, 2, null, 11, null, null, 1]
   10
   / \
  5  -3
 / \   \
3   2   11
   / 
  1
  • Expected Output: 3
  • Justification: The path that sums to 18 is:
    • 10 → 5 → 3
    • 10 → -3 → 11
    • 10 → 5 → 2 → 1

Constraints:

  • The number of nodes in the tree is in the range [0, 1000].
  • -10<sup>9</sup> <= Node.val <= 10<sup>9</sup>
  • -1000 <= targetSum <= 1000

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible