// Arup Guha
// 12/5/2023
// Code for 2023 COP 3502 Final Exam Part B Question 8 - Both Versions

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

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

int sumdepthk(treenode* root, int k);
treenode* insert(treenode* root, int val, int path, int steps);
treenode* makeNode(int val);
void preorder(treenode* root);
int summaxpath(treenode* root);

int main() {

    // Example from depth problem.
    treenode* tr = NULL;
    tr = insert(tr, 20, 0, 0);
    preorder(tr); printf("\n");
    tr = insert(tr, 3, 0, 1);
    preorder(tr); printf("\n");
    tr = insert(tr, 22, 1, 1);
    preorder(tr); printf("\n");
    tr = insert(tr, 21, 0, 2);
    preorder(tr); printf("\n");
    tr = insert(tr, 10, 2, 2);
    preorder(tr); printf("\n");
    tr = insert(tr, 14, 1, 2);
    preorder(tr); printf("\n");
    tr = insert(tr, 6, 2, 3);
    preorder(tr); printf("\n");

    // Test depth.
    printf("%d\n", sumdepthk(tr, 2));

    // Note the tree here is different than the one drawn in the question.
    printf("%d\n", summaxpath(tr));

    // Free tree.
    freetree(tr);

    return 0;
}

// Returns the sum of all nodes at a depth of k in the tree rooted at root.
int sumdepthk(treenode* root, int k) {

    // Be safe!
    if (root == NULL) return 0;

    // Only this node fits the bill.
    if (k == 0) return root->data;

    // Just try both sides and add.
    return sumdepthk(root->left, k-1) + sumdepthk(root->right, k-1);
}

// Returns the max sum of any path from root to leaf.
int summaxpath(treenode* root) {

    // Get this out of the way.
    if (root == NULL) return 0;

    // Try both.
    int left = summaxpath(root->left);
    int right = summaxpath(root->right);

    // left is better add it to root.
    if (left > right)
        return left + root->data;

    // If we get here, right is better.
    return right + root->data;
}

// Inserts a node storing val into the tree pointed to by root via the path stored in the bits of bit
// that is exactly step # of steps.
treenode* insert(treenode* root, int val, int path, int steps) {

    // Easy case.
    if (root == NULL) return makeNode(val);

    // Do iteratively.
    treenode* itr = root;
    for (int i=0; i<steps-1; i++) {

        // If this bit is one, go right.
        if (path&1) itr = itr->right;

        // Otherwise left.
        else itr = itr->left;

        // Shift the lsb out of the way.
        path >>= 1;
    }

    // Deal with last bit. Tells us where node goes.
    if (path)
        itr->right = makeNode(val);
    else
        itr->left = makeNode(val);

    // Ta da!
    return root;
}

// Runs a preorder traversal on the tree pointed to by root, printing the items.
void preorder(treenode* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

// Creates a node storing val, returning a pointer to it.
treenode* makeNode(int val) {
    treenode* tmp = malloc(sizeof(treenode));
    tmp->data = val;
    tmp->left = NULL;
    tmp->right = NULL;
    return tmp;
}


// Frees memory allocated for all nodes in tree pointed to by root.
void freetree(treenode* root) {
    if (root == NULL) return;
    freetree(root->left);
    freetree(root->right);
    free(root);
}