#include <stdio.h>
#include <stdlib.h>

struct _node {
    struct _node *left;
    int data;
    struct _node *right;
};

struct _node* new_node(struct _node* left, int data, struct _node* right) {
    struct _node* ret = (struct _node*)malloc(sizeof(struct _node));
    ret->left = left;
    ret->data = data;
    ret->right = right;
    return ret; 
}

int sum_tree(struct _node *tree) {
    if (tree == NULL) {
        return 0;
    } else {
        return tree->data + sum_tree(tree->left) + sum_tree(tree->right);
    } 
}

int main(void) {

    struct _node* test0 = new_node(new_node(new_node(NULL, 1, NULL),
                                            6, 
                                            new_node(NULL, 11, NULL)),
                                   4,                
                                   new_node(new_node(NULL, 4, NULL),
                                            5, 
                                            new_node(NULL, 0, NULL)));
    struct _node* test1 = new_node(test0, 8, test0);    
    struct _node* test2 = new_node(test1, 9, test1);  
    struct _node* test3 = new_node(test2, 10, test1); 

    printf("The sum of test0 is %d.\n", sum_tree(test0));
    printf("The sum of test1 is %d.\n", sum_tree(test1));
    printf("The sum of test2 is %d.\n", sum_tree(test2));
    printf("The sum of test3 is %d.\n", sum_tree(test3));
    return 0;       
}