View difference between Paste ID: CPbuFpKc and 4FqUdC6J

 #include<stdio.h>
 #include<stdlib.h>
 
 #define bool int
 
 /* A binary tree node has data, pointer to left child
    and a pointer to right child */
 struct node
 {
    int data;
    struct node* left;
    struct node* right;
 };
 
 /*
  Original example code.
 
  Given a tree and a sum, return true if there is a path from the root
  down to a leaf, such that adding up all the values along the path
  equals the given sum.
 
  Strategy: 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.
 */
 bool hasPathSum_original(struct node* node, int sum)
 {
   /* return true if we run out of tree and sum==0 */
   if (node == NULL)
   {
      return (sum == 0);
   }
 
   else
   {
     bool ans = 0;
 
     /* otherwise check both subtrees */
     int subSum = sum - node->data;
 
     /* If we reach a leaf node and sum becomes 0 then return true*/
     if ( subSum == 0 && node->left == NULL && node->right == NULL )
       return 1;
 
     if(node->left)
       ans = ans || hasPathSum_original(node->left, subSum);
     if(node->right)
       ans = ans || hasPathSum_original(node->right, subSum);
 
     return ans;
   }
 }
 
 /*
-Here is the original example without optimization. You'll see that the algorithm is much cleaner now. You had a bug in your rewrite as it answered the question "Is there A path with the given sum?" when you had nodes which had a left node without a right one (or vice versa).
+Here is the original example without optimization. You'll see that the algorithm is much cleaner now.
 Note that this will short-circuit the calls in the line with the return statement.
 */
 bool hasPathSum_revised(struct node* node, int sum)
 {
   /* return true if we run out of tree and sum==0 */
   if (node == NULL)
      return (sum == 0);
 
   /* otherwise check both subtrees */
   int subSum = sum - node->data;
   return hasPathSum_revised(node->left, subSum) ||  hasPathSum_revised(node->right, subSum);
 }
 
 /*
 Find the minimum in the binary tree - without making any assumptions.
 Call this with an "impossible" minimum at top level.
 */
 int findMin(struct node* node, int min) {
     if (!node) return min;
     if (node->data < min)
        min = node->data;
 
     int leftMin = findMin(node->left, min);
     if(leftMin < min)
        min = leftMin;
 
     int rightMin = findMin(node->right, min);
     if(rightMin < min)
        min = rightMin;
 
     return min;
 }
 
 /* UTILITY FUNCTIONS */
 /* Helper function that allocates a new node with the
    given data and NULL left and right pointers. */
 struct node* newnode(int data)
 {
   struct node* node = (struct node*)
                        malloc(sizeof(struct node));
   node->data = data;
   node->left = NULL;
   node->right = NULL;
 
   return(node);
 }
 
 void freetree(struct node* node)
 {
   if(!node)
     return;
   freetree(node->left);
   freetree(node->right);
   free(node);
 }
 
 /* Generate a random full binary tree where every path to a leaf has the
    totalsum given */
 struct node* generatetree(struct node* node, unsigned depth, int totalsum) {
   if(depth == 0) {
     node->data = totalsum;
     return node;
   }
   node->data = (rand() % 100) - 50;
   node->left = newnode(0);
   node->right = newnode(0);
   generatetree(node->left, depth-1, totalsum - node->data);
   generatetree(node->right, depth-1, totalsum - node->data);
   return node;
 }
 
 void inspecttree(struct node* root, int expected_sum) {
   printf("Original:\n");
   if(hasPathSum_original(root, expected_sum))
     printf("There is a root-to-leaf path with sum %d\n", expected_sum);
   else
     printf("There is no root-to-leaf path with sum %d\n", expected_sum);
 
   printf("Revised:\n");
   if(hasPathSum_revised(root, expected_sum))
     printf("There is a root-to-leaf path with sum %d\n", expected_sum);
   else
     printf("There is no root-to-leaf path with sum %d\n", expected_sum);
   /* where was INT_MAX defined again :( */
   printf("Minimum: %d\n", findMin(root, 60000));
 }
 
 /* Driver program to test above functions*/
 int main()
 {
   srand(time(NULL));
   int sum = 21;
 
   /* Hand constructed binary tree is
             10
           /   \
         8      2
       /  \    /
     3     5  2
   */
   struct node *root = newnode(10);
   root->left        = newnode(8);
   root->right       = newnode(2);
   root->left->left  = newnode(3);
   root->left->right = newnode(5);
   root->right->left = newnode(2);
   inspecttree(root, sum);
   freetree(root);
 
   root = generatetree(newnode(0), 8, 1000);
   inspecttree(root, 1000);
   freetree(root);
 
   getchar();
   return 0;
 }