// Arup Guha
// 3/17/2016
// Written in COP 3502 (updated on 3/24/2016 to include bfs traversal.)

// Edited on 11/5/2021 to just include solutions to Binary Tree Questions from Fall 2021 Quiz #4 

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

// Used for a binary tree node.
typedef struct bintreenode {
    int data;
    struct bintreenode* left;
    struct bintreenode* right;
} btreenode;

// Support Functions.
btreenode* insert(btreenode* root, int value);
void freeTree(btreenode* root);

// Quiz Questions
int getAdjustedSum(btreenode* root);
int countLeafNodes(btreenode* root);

int main() {

    // Create tree from class notes.
    btreenode* mytree = NULL;
    mytree = insert(mytree, 10);
    mytree = insert(mytree, 5);
    mytree = insert(mytree, 15);
    mytree = insert(mytree, 3);
    mytree = insert(mytree, 7);
    mytree = insert(mytree, 4);
    mytree = insert(mytree, 9);
    mytree = insert(mytree, 13);
    mytree = insert(mytree, 11);
    mytree = insert(mytree, 14);
    printf("adj sum: %d\n", getAdjustedSum(mytree));
    printf("# leaf nodes: %d\n", countLeafNodes(mytree));
    freeTree(mytree);

    return 0;
}

// Returns the desired adjusted sum.
int getAdjustedSum(btreenode* root) {

	// Nothing to add.
    if (root == NULL) return 0;

	// By subtracting the recursive calls, we get the desired alternating behavior.
    return root->data - getAdjustedSum(root->left)
                      - getAdjustedSum(root->right);

}

// Returns the number of leaf nodes in the tree rooted at root.
int countLeafNodes(btreenode* root) {
	
	// No nodes...
    if (root == NULL) return 0;
	
	// A leaf node!
    if (root->left == NULL && root->right == NULL) return 1;
	
	// Recursively add the rest.
    return countLeafNodes(root->left) + countLeafNodes(root->right);
}

// Inserts a new node into the tree rooted at root with data set to value.
// and returns a pointer to the root of the resulting tree.
btreenode* insert(btreenode* root, int value) {

    // Inserting into an empty tree.
    if (root == NULL) {
        btreenode* temp = malloc(sizeof(btreenode));
        temp->data = value;
        temp->left = NULL;
        temp->right = NULL;
        return temp;
    }

    // Go left.
    if (value < root->data)
        root->left = insert(root->left, value);

    // Go right.
    else
        root->right = insert(root->right, value);

    // Must return the root of this tree.
    return root;
}

// Frees all nodes in the tree rooted at root.
void freeTree(btreenode* root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}