Path sum equal to k in trees

You are given a binary tree which can have negative elements also and an integer k, you need to print all the paths in the tree which has sum equal to k. Note that the paths need not necessarily be from root to leaf nodes. It can start from any node and can end to any node in the tree and must be a downward path only.

Consider the example below.

Input : k = 5  
        Root of below binary tree:
           1
        /     \
      3        -1
    /   \     /   \
   2     1   4     5                        
        /   / \     \                    
       1   1   2     6    
                       
Output :
3 2 
3 1 1 
1 3 1 
4 1 
1 -1 4 1 
-1 4 2 
5 
1 -1 5 

Algorithm

  1. With the help of simple preorder traversal and backtracking, we can solve the problem easily.
  2. Here each node can be treated a root node and thus, the path can start and end at any node.
  3. We also keep track of the current path so that if the sum is equal to k, we can print the path. For this, we keep storing the visited nodes in a vector.
  4. At each node, we check whether the current path sum is equal to k or not, if yes, we print the path. Note that we need to traverse the entire path as there can be negative elements too.
  5. We then backtrack by removing the current node.

For better understanding, look at the code below.

#include <bits/stdc++.h>
using namespace std;

struct Node{
  Node* left;
  Node* right;
  int data;
};

Node* createNode(int key){
    Node* temp = new Node();
    temp->data = key;
    temp->right = nullptr;
    temp->left = nullptr;
    return temp;
}

Node* root = nullptr;

Node* insertNode(Node* node, int key){
    Node* temp = createNode(key);
    if(root == nullptr){
        root = temp;
        return root;
    }
    if(node == nullptr){
        return temp;   
    }
    
    if(key < node->data){
        node->left = insertNode(node->left, key);
    }else if(key > node->data){
        node->right = insertNode(node->right, key);
    }
    return node;
}

void levelOrderTraversal(Node* root){
    Node* temp = root;
    queue<Node*> q;
    q.push(temp);
    while(!q.empty()){
        Node* front = q.front();
        cout<<front->data<<" ";
        q.pop();
        if(front->left != nullptr){
            q.push(front->left);
        }
        if(front->right != nullptr){
            q.push(front->right);
        }
    }
}


void helper(Node *root, vector<int>& path, int k) 
{ 
    if (!root){
        return;
    }
    // add current node to the path 
    path.push_back(root->data); 
  
    // check if there's any k sum path in the left sub-tree. 
    helper(root->left, path, k); 
  
    // check if there's any k sum path in the right sub-tree. 
    helper(root->right, path, k); 
  
    // check if there's any k sum path that terminates at this node 
    // Traverse the entire path as there can be negative elements too 
    int curr_sum = 0; 
    for (int i=path.size()-1; i>=0; i--) 
    { 
        curr_sum += path[i]; 
  
        // If path sum is k, print the path 
        if (curr_sum == k){
            for(int j=i; j<path.size(); j++){
                cout<<path[j]<<" ";
            }
            cout<<endl;
        }
    } 
  
    // Remove the current element from the path 
    path.pop_back(); 
} 

int main()
{
    insertNode(root, 1);
    root->left = createNode(3);
    root->left->left = createNode(2);
    root->left->right = createNode(1);
    root->left->right->left = createNode(1);
    root->right = createNode(-1);
    root->right->left = createNode(4);
    root->right->right = createNode(5);
    root->right->left->left = createNode(1);
    root->right->left->right = createNode(2);
    root->right->right->right = createNode(6);
    int k = 5;
    cout<<"The level Order traversal is: \n"<<endl;
    levelOrderTraversal(root);
    cout<<endl<<endl;
    vector<int> path;
    cout<<"The paths with sum "<<k<<" are:\n"<<endl;
    helper(root, path, k);
    return 0;
}

Also, check out another popular interview problem Number of islands.

One comment

Leave a Reply

Your email address will not be published.