language: C (gcc-4.7.2)
date: 815 days 0 hours ago
link:
visibility: private 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
 
typedef struct treeNode* treeNodePtr;
struct treeNode{
        int data;
        treeNodePtr left;
        treeNodePtr right;
};
 
treeNodePtr newNode(int data) {
        treeNodePtr newNode = malloc(sizeof(struct treeNode));
        if(!newNode) {
                fprintf(stderr,"Error allocating memory\n");
                exit(1);
        }
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
 
        return newNode;
}
 
bool hasPathSum(treeNodePtr node, int sum) {
        // CASE 1: empty tree.
        if (node == NULL) {
                return sum == 0;
        }
 
        // CASE 2: Tree exits.
        int subSum = sum - node->data;
        // CASE 2A: Function is called on a leaf node.
        if (node->left==NULL && node->right==NULL) {
                return subSum == 0;
                // CASE 2B: Function is called on a non-leaf node.
        } else {
                // CASE 2BA: Non-left node has desired path in left subtree.
                if (node->left != NULL && hasPathSum(node->left, subSum) ){
                        return true;
                }
                // CASE 2BB: Non-left node has desired path in right subtree.
                if ( node->right != NULL && hasPathSum(node->right, subSum) ) {
                        return true;
                }
                // CASE 2BC: Non-left node has no desired pat.
                return false;
        }
}
 
int main() {
 
/*
           5
          / \
         2   1
        /    
       3
*/
 
        treeNodePtr root = newNode(5);
        root->left       = newNode(2);
        root->right      = newNode(1);
        root->left->left = newNode(3);
 
        int tests[] = {1,2,3,5,6,7,8,10};
        int size = sizeof(tests)/sizeof(*tests);
        int i;
 
        for(i=0;i<size;i++) {
                if(hasPathSum(root,tests[i])) {
                        printf("Root to leaf path of sum %d exits\n",tests[i]);
                }
        }
 
        return 0;
}