Root to leaf path sum equal to a given number

Hello Everyone,

Given a binary tree and a number, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given number. Return false if no such path can be found.

For example, in the above tree root to leaf paths exist with following sums.
21 –> 10 – 8 – 3
23 –> 10 – 8 – 5
14 –> 10 – 2 – 2
So the returned value should be true only for numbers 21, 23 and 14. For any other number, returned value should be false.

Algorithm:
Recursively check if left or right child has path sum equal to ( number – value at current node)
Implementation:

#include <bits/stdc++.h>

using namespace std;

#define bool int

/* A binary tree node has data, pointer to left child

and a pointer to right child */

class node

{

public :

int data;

node* left;

node* right;

};

/*

Given a tree and a sum, return true if there is a path from the root

down to a leaf, such that adding up all the values along the path

equals the given sum.

Strategy: subtract the node value from the sum when recurring down,

and check to see if the sum is 0 when you run out of tree.

*/

bool hasPathSum(node* Node, int sum)

{

/* return true if we run out of tree and sum==0 */

if (Node == NULL)

{

return (sum == 0);

}

else

{

bool ans = 0;

int subSum = sum - Node->data;

/* If we reach a leaf node and sum becomes 0 then return true*/

if ( subSum == 0 && Node->left == NULL && Node->right == NULL )

return 1;

/* otherwise check both subtrees */

if (Node->left)

ans = ans || hasPathSum(Node->left, subSum);

if (Node->right)

ans = ans || hasPathSum(Node->right, subSum);

return ans;

}

}

/* UTILITY FUNCTIONS */

/* Helper function that allocates a new node with the

given data and NULL left and right pointers. */

node* newnode( int data)

{

node* Node = new node();

Node->data = data;

Node->left = NULL;

Node->right = NULL;

return (Node);

}

// Driver Code

int main()

{

int sum = 21;

node *root = newnode(10);

root->left = newnode(8);

root->right = newnode(2);

root->left->left = newnode(3);

root->left->right = newnode(5);

root->right->left = newnode(2);

if (hasPathSum(root, sum))

cout << "There is a root-to-leaf path with sum " << sum;

else

cout << "There is no root-to-leaf path with sum " << sum;

return 0;

}

Output

There is a root-to-leaf path with sum 21

Time Complexity : O(n)