Untitled

class Solution{  //O(n2)
  public:
  
    int count=0;
    void preorder(Node *root, int k, unordered_map<int,int>&mp,int prev)
    {
        if(root)
        {
            int curr=prev+root->data ;
            if(mp.find(curr-k)!=mp.end()){ //curr-k is found in mp
                count+=mp[curr-k];         //
            }
      
            if(curr==k){
                  count++;
            }
      
             mp[curr]++;
            
            preorder(root->left,k,mp,curr);
            preorder(root->right,k,mp,curr);
            
              mp[curr]--;
        }
    }
    int sumK(Node *root,int k)
    {
        unordered_map<int,int>mp;//mp stores sum of node values and the number of
      //                               times those node values have appeared
        preorder(root,k,mp,0);
        return count ;
    }
};