Grokking Tree Coding Patterns for Interviews

0% completed

​

Count Paths for a Sum (medium)

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

Try it yourself

.....

.....

.....

Like the course? Get enrolled and start learning!
R

Ray

· 4 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
I

Interviews

· 5 years ago

struggled with this question. missed having to find all sub paths of current node and using reverse iterator to do this. Why doesn't a regular iterator work?

Show 1 reply
A

Alfonso Vieyra

· 4 years ago

Why do we have to instantiate pathCount to 0? When i dont do that, i get an overcount. Does anyone know why that is? I've seen it previous problems but i don't really understand why we do it.

A

Avinash Agarwal

· 4 years ago

int count =0; HashMap hmap = new HashMap();

public int pathSum(TreeNode root, int targetSum) { pathSum(root, 0, targetSum); return count; }

private void pathSum(TreeNode node, int curSum, int targetSum) { if(node == null) return;

curSum += node.val;

if(curSum == targetSum) count++;

count += hmap.getOrDefault(curSum-targetSum, 0);

hmap.put(curSum, hmap.getOrDefault(curSum, 0) + 1);

pathSum(node.left, curSum, targetSum); pathSum(node.right, curSum, targetSum);

hmap.put(curSum, hmap.get(curSum) -1); }

Show 1 reply
A

Athanasios Petsas

· 4 years ago

I think we don't need the list neither the backtracking. We can just do two recursive calls for each child (one passing the sum as is and one with the current node's value subtracted from the sum) in order to cover all the possible cases. So the time and space complexity will be O(N). Sample code in C++:

{code} int pathsWithSum(TreeNode *root, int sum) { int totalPaths = 0; pathsWithSumHelper(root, sum, totalPaths); return totalPaths; }

void pathsWithSumHelper(TreeNode *root, int sum, int & totalPaths) { if (root == nullptr) return;

if (root->val == sum) { totalPaths += 1; }

// we are at a leaf node if (root->left == nullptr && root->right == nullptr) return;

// not leaf pathsWithSumHelper(root->left, sum, totalPaths); pathsWithSumHelper(root->left, sum - root->val, totalPaths); pat

Show 4 replies
H

hj3yoo

· 4 years ago

How is the current implementation checking sum of every possible sub-paths? The for loop just goes through the current traversal and adds starting from the root to the current node.

Shouldn't there be either a 2D for-loop or a sliding window?

Show 1 reply
S

sevillaarvin

· 3 years ago

Anyone have a good resource for Prefix Sum? I'd like to understand it more intuitively.

R

random979

· 3 years ago

My code is as follows

public int counter = 0;

public int countPaths(TreeNode root, int S) {
    if (root == null) return 0;
    dfs(root, S, new ArrayList<>());
    return counter;
}

public void dfs(TreeNode root, int S, List<Integer> currentSequence) {
    if (root == null) return;

    currentSequence.add(root.val);
    if (root.left == null && root.right == null) {
        // check if any ordered subset has S
        int pathSum = 0;
        ListIterator<Integer> pathIterator = currentSequence.listIterator(currentSequence.size());
        while (pathIterator.hasPrevious()) {
            pathSum += pathIterator.previous();
            // if the sum of any sub-path is equal to 'S' we increment our path count.
            if (pathSum == S) {
                counter++;
Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

#class TreeNode:
#  def __init__(self, val, left=None, right=None):
#    self.val = val
#    self.left = left
#    self.right = right

class Solution:

  def __init__(self):
    # the result counter 
    self.counter = 0 
    
  '''
    node = the node to process 
    path = top to down path of the nodes in the current recursion
    target = the target sum 
    add = accumulative addition 
    start = start index 
    end = end index
  '''
  def dfs(self, node, path, target, add, start, end):
    if not node:
      return 

    # append the new node to the path and end
    path.append(node.val)
    add += node.val

    # if the node itself = target
    if node.val == target:
      self.counter += 1
    else:  
      # else find a sub-path "moving window" = target. and move th
L

lejafilip

· 2 years ago

It looks like doable but we need to store every value in array.