# Interview Questions

Ritambhara Technologies - Coding Interview Preparations > Interview Questions > Algorithms > Has Path Sum (binary tree)

# Has Path Sum (binary tree)

- June 11, 2012
- Posted by: Kamal Rawat
- Category: Algorithms

No Comments

Given a Binary Tree and a number **x**, Write a function to see if there exist a root to leaf path in the tree whose sum is equal to **x**.

### Solution:

**For Example:** Let us consider the below tree:

There are only three root to leaf paths in the tree

**10 – 5 – 4 – 1****10 – 5 – 8****10 – 30 – 40**

**Algorithm:**

If x = 20, then the problem “find a path in the tree **(with root at 10), whose sum is 20**” can be broken into

- Find a path in the tree with
**root at 5**, whose**sum is 10**(20 – 10). - Find a path in the tree with
**root at 30**, whose**sum is 10**(20 – 10).

We will return true if any of the below recursive call returns true.

**Code:**

The below function will return true if there exist a path in the tree with sum = x, else it will return false.

/* returns true if there exists a path in the tree whose sum = x */ bool hasPathSum(node* r, int x){ // If null tree and x == 0 then return true if(0 == x) return r ? false : true; if(r) { // If leaf node then its data should be x if ( NULL == r->left && NULL == r->right ) return !(x – r->data); // If only right sub-tree then check in right only if(NULL == r->left) return hasPathSum(r->right, x – r->data); // If only LEFT sub-tree then check in left only if(NULL == r->right) return hasPathSum(r->left, x – r->data); // Check both left & right sub trees return ( hasPathSum(r->left, x – r->data) || hasPathSum(r->right, x – r->data) ); } else return false; }