// Arup Guha
// 4/25/2024
// Solution to Spring 2024 COP 3502H Final Exam Question 11

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

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

int numdominating(bintreenode* root);
bintreenode* mkNode(int val);
void freetree(bintreenode* root);

int main(void) {

    // I've built a test here, the answer is 7. Nodes are 8, 7, 6, 5, 11, 3 and 2.
    bintreenode* n1 = mkNode(8);
    bintreenode* n2 = mkNode(4);
    bintreenode* n3 = mkNode(7);
    n1->left = n2; n1->right = n3;
    bintreenode* n4 = mkNode(6);
    n3->left = n4;
    bintreenode* n5 = mkNode(9);
    bintreenode* n6 = mkNode(5);
    n2->left = n5; n2->right = n6;
    bintreenode* n7 = mkNode(11);
    n5->right = n7;
    bintreenode* n8 = mkNode(3);
    bintreenode* n9 = mkNode(2);
    n6->left = n8; n6->right = n9;

    // Run it.
    printf("numd = %d\n", numdominating(n1));

    // Free memory.
    freetree(n1);

    return 0;
}

// Frees the memory in the tree pointed to by root.
void freetree(bintreenode* root) {
    if (root == NULL) return;
    freetree(root->left);
    freetree(root->right);
    free(root);
}

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

// Answer to the question.
int numdominating(bintreenode* root) {

    // No node shere.
    if (root == NULL) return 0;

    // This was defined in the problem.
    if (root->left == NULL && root->right == NULL) return 1;

    // Easiest to set default to 1 and then overwrite 0, if necessary.
    int score = 1;
    if (root->left != NULL && root->data <= root->left->data)
        score = 0;
    if (root->right != NULL && root->data <= root->right->data)
        score = 0;

    // Now add score and recurse to both sides.
    return score + numdominating(root->left)
                 + numdominating(root->right);
}