15.md

K SUM PATH

METHOD 1 (TC-0(N^2))

 int ans=0;
    
    void func(Node* root,vector<int>& path,int k)
    {
        if(!root)
            return;
            
        path.push_back(root->data);
        func(root->left,path,k);
        func(root->right,path,k);
        
        
        int f=0;
        
        for(int i=path.size()-1;i>=0;i--)
        {
            f+=path[i];
            if(f==k)
                ans++;
        }
        path.pop_back();
    }
    int sumK(Node *root,int k)
    {
        vector<int> path;
        func(root,path,k);
        return ans;
    }

METHOD 2

 int mod=1e9 +7;
    int func(Node *root,int k,unordered_map<int,int>&m,int sum)
    {
        if(!root)
            return 0;
        
        int c=0;
            
        sum +=root->data;  //add the current node valye to sum
        
        if(m.find(sum-k)!=m.end())
            c+=m[sum-k] %mod;
            
        m[sum]++;
        
        int left=func(root->left,k,m,sum);
        int right=func(root->right,k,m,sum);
        
        m[sum]--;
        
        return c+left+right;
    }
    int sumK(Node *root,int k)
    {
        // code here 
        
        unordered_map<int,int>m;
        
        m[0]++;   //current sum is zero
        
        int sum=0;
        
        return func(root,k,m,sum);
       
    }