Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Count Paths for a Sum

Problem Statement

Given a binary tree and a number ‘S’, find all paths in the tree such that the sum of all the node values of each path equals ‘S’. Please note that the paths can start or end at any node but all paths must follow direction from parent to child (top to bottom).

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

Solution

This problem follows the Binary Tree Path Sum pattern. We can follow the same DFS approach. But there will be four differences:

1

.....

.....

.....

Like the course? Get enrolled and start learning!
R

Ray

· 5 years ago

The solution works, but confused about the backtracking (currentPath.pop();)

After currentPath.pop(); is called, I don't understand how the recursive function (count_paths_recursive()) is called again.

The tree traversal has already happened above with the left & right child nodes. Popping the currentPath array (removing last value) wouldn't call count_paths_recursive() again...

Show 2 replies