Given Binary Tree and sum, give root to leaf path such that all nodes add to that sum

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);

will return true.

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, stackoverflow
Thanks