#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.
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;
}