Monday, November 24, 2008

hadPathSum - Tree Problem

I have found one problem at : http://cslibrary.stanford.edu/110/BinaryTrees.html

hasPathSum()

----------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------
We'll define a "root-to-leaf path" to be a sequence of nodes in a tree starting with the root node and proceeding downward to a leaf (a node with no children). We'll say that an empty tree contains no root-to-leaf paths. So for example, the following tree has exactly four root-to-leaf paths:

5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1

Root-to-leaf paths:
path 1: 5 4 11 7
path 2: 5 4 11 2
path 3: 5 8 13
path 4: 5 8 4 1

For this problem, we will be concerned with the sum of the values of such a path -- for example, the sum of the values on the 5-4-11-7 path is 5 + 4 + 11 + 7 = 27.

Given a binary tree and a sum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Return false if no such path can be found. (Thanks to Owen Astrachan for suggesting this problem.)

int hasPathSum(struct node* node, int sum);

----------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------


After solving this when I matched the solution, I disagree with the provided solution. It will calculate 5- 8- 4 as path.
Provided solution is:

int hasPathSum(struct node* node, int sum) {
// return true if we run out of tree and sum==0
if (node == NULL) {
return(sum == 0);
}
else {
// otherwise check both subtrees
int subSum = sum - node->data;
return(hasPathSum(node->left, subSum) ||
hasPathSum(node->right, subSum));
}
}

Here it is not calculating tree leaf properly.

I have write following code.


bool hasPathSum(TNodeRef root, int data){
if(!root) return (false); // Will come to this when node have only right or left node (mean not leaf)
if(root->left == NULL && root->right == NULL) return data == root->data;
data -=root->data;
return( hasPathSum(root->left, data)||
hasPathSum(root->right, data));
}

Please comment if this too have mistake.

:)




2 comments:

Akash said...

I'm not getting anything wrong in original solution. Yours is same as that one.

Unknown said...

I think both the solutions are fine. In earlier one, there is no check for root->left==NULL and root->left==NULL. But it is not required as when hasPathSum() is called with root=NULL, it simply compare if root->data==0. So it works fine. One more thing is that earlier solution is more readable.