Grokking Tree Coding Patterns for Interviews
Vote

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!
O

origamimathematician

· 6 months ago

You are missing some test cases when submitting. I created a solution that 'passes' all cases when submitted but it's incorrect:

class Solution:
  def countPaths(self, root, S):
    observed = {0: True}

    def traverse(node, target, prefix_sum):
      if node is None:
        return 0
        
      prefix_sum = node.val + prefix_sum

      curr_req_sum = prefix_sum - target
      seen = int(observed.get(curr_req_sum, False))

      observed[prefix_sum] = True

      res = seen + traverse(node.left, target, prefix_sum) + traverse(node.right, target, prefix_sum)

      observed[prefix_sum] = False
      return res

    return traverse(root, S, 0)

This fails the following test case since it does not count frequencies of prior sums correctly:

[0,0,null,0]

0

But submit ac

Ali Simsek

Ali Simsek

· 2 years ago

class Solution {
  public int countPaths(TreeNode root, int S) {
    int[] count = new int[1];

    traverse(root, count, S);
    return count[0];
  }

  private void traverse(TreeNode root, int[] count, int S){
    if(root == null) return;

    calc(root,count,S,0);

    traverse(root.left, count, S);
    traverse(root.right,count, S);
  }

  private void calc(TreeNode root, int[] count, int S, int curr){
    if(root == null) return;

    curr += root.val;
    
    if(curr == S) count[0]++;

    calc(root.left,count, S, curr);
    calc(root.right,count, S, curr);
  } 
}
Debasis B

Debasis B

· 2 years ago

    public int countPaths(TreeNode root, int targetSum)
    {
        int count = 0;
        countPaths(root, targetSum, ref count, new List<int>());
        return count;
    }

    private void countPaths(TreeNode root, int targetSum, ref int count, List<int> sumList)
    {
        // base case
        if (root == null)
        {
            return;
        }
        // add curr node val to each sums and a separate sum
        // => curr val added to prev paths and new path created starting from curr
        for (int i = 0; i < sumList.Count; i++)
        {
            sumList[i] += root.Val;
        }
        sumList.Add(root.Val);
        // check if there's a  valid sum
        foreach (int sum in sumList)
        {
            if (sum == targetSum)
            {
L

lejafilip

· 2 years ago

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

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
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
S

sevillaarvin

· 3 years ago

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

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
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

Reading Progress

0%

Vote for new content