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.
**Problem 1**
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.
**Solution:**
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.
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));
}
}
Though this solution looks good, but it can have some flaws.Consider the case :
5
/ \\
2 1
/
3
Call the above function
hasPathSum(root, 7);
But there is no root-to-leaf path that adds to 7. That's because when node `2` is reached, it recursively checks the right child (with sum 0), which then returns true because the right child is `null`.
This will return true, when the recursion is at node 2, and right null leave call will return true.
_Correct solution_
Lets fix it: if statement should check children and return statement deduct node.data from sum
boolean hasPathSum(Node node, int sum) {
int subSum = sum - node.data;
if(node.left==null && node.right==null) {
return(subSum == 0);
}
else {
// otherwise check both subtrees
if ( node.left != null && hasPathSum(node.left, subSum) ) {
return true;
if ( node.right != null && hasPathSum(node.right, subSum) ) {
return true;
}
return false;
}
}
You can roll the else block into one long statement if you want (lots of ands and ors), but I find this cleaner.
**Problem 2**
Given a binary tree, print out all of its root-to-leaf paths as defined above. This problem is a little harder than it looks, since the "path so far" needs to be communicated between the recursive calls.
**Hint:** In C, C++, and Java, probably the best solution is to create a recursive helper function printPathsRecur(node, int path\[\], int pathLen), where the path array communicates the sequence of nodes that led up to the current call. Alternately, the problem may be solved bottom-up, with each node returning its list of paths. This strategy works quite nicely in Lisp, since it can exploit the built in list and mapping primitives.
Given a binary tree, print out all of its root-to-leaf paths, one per line.
void printPaths(struct node* node) {
int path[1000]; printPathsRecur(node, path, 0);
}
/*
Recursive helper function – given a node, and an array containing
the path from the root node up to but not including this node,
print out all the root-leaf paths.
*/
void printPathsRecur(struct node* node, int path[], int pathLen) {
if (node==NULL) return;
// append this node to the path array
path[pathLen] = node->data;
pathLen++;
// it’s a leaf, so print the path that led to here
if (node->left==NULL && node->right==NULL) {
printArray(path, pathLen);
}
else {
// otherwise try both subtrees
printPathsRecur(node->left, path, pathLen);
printPathsRecur(node->right, path, pathLen);
}
}
// Utility that prints out an array on a line.
void printArray(int ints[], int len) {
int i;
for (i=0; i
printf("%d “, ints[i]);
}
printf("\n”);
}
**Reference** \- [stanford](http://cslibrary.stanford.edu/110/BinaryTrees.html), [stackoverflow](http://stackoverflow.com/questions/4214859/binary-tree-haspathsum-implementation)
Thanks