// Arup Guha
// 7/27/2020
// Solution to 2020 Summer COP 3502 Final Exam Part B Q1

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

typedef struct node {
    int data;
    struct node* left;
    struct node* right;
} node;

int numEvenNodes(node* root);
node* insert(node* root, int val);
node* newNode(int x);
void freeTree(node* root);

int main(void) {

    // Our test.
    node* tree = NULL;
    tree = insert(tree, 17);
    tree = insert(tree, 12);
    tree = insert(tree, 29);
    tree = insert(tree, 34);
    tree = insert(tree, 48);
    tree = insert(tree, 16);
    tree = insert(tree, 7);
    printf("%d\n", numEvenNodes(tree));
    freeTree(tree);
    return 0;
}

// Returns the # of nodes storing even values in the tree rooted at root.
int numEvenNodes(node* root) {

    // Nothing in this tree.
    if(root == NULL) return 0;

    // Set res to 1 if the root is even, 0 otherwise.
    int res = 0;
    if (root->data%2 == 0) res++;

    // Now, add in the contributions of both subtrees and return.
    return res + numEvenNodes(root->left) + numEvenNodes(root->right);
}

// Regular BST insert.
node* insert(node* root, int val) {

    if (root == NULL) return newNode(val);

    if (val < root->data)   root->left = insert(root->left, val);
    else                    root->right = insert(root->right, val);

    return root;
}

// Returns a new node storing x.
node* newNode(int x) {
    node* res = malloc(sizeof(node));
    res->data = x;
    res->left = NULL;
    res->right = NULL;
    return res;
}

// Frees all the memory associated with the tree pointed to by root.
void freeTree(node* root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}