MCN Professionals | Interview Question of the day
|
Date: 8th
Sept; 2011
|
Difficulty Level: ****
|
Category: Programming
|
|
To receive one
interview question in your mailbox daily, please subscribe to "A
Question A Day" at MCN Professionals home page.
|
Today's Question:
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;
}
}
Interview Questions Archive:
To see all the questions in the category, click here...
------------------------------------------------------------------------------------------------------------