Untitled

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

typedef struct BST_Node_Struct {
  double data;
  struct BST_Node_Struct *left;
  struct BST_Node_Struct *right;
} BST_Node;

BST_Node *new_BST_Node(double key) {
  BST_Node *new_node = NULL;
  new_node = (BST_Node *)calloc(1, sizeof(BST_Node));

  new_node->data = key;
  new_node->left = NULL;
  new_node->right = NULL;

  return new_node;
}

BST_Node *BST_insert(BST_Node *root, BST_Node *new_node) {
    if (root == NULL) return new_node;
    if (fabs(root->data - new_node->data) < 1e-15) printf("Duplicate node requested %f, it was ignored\n", root->data);
    else if (root->data > new_node->data) root->left = BST_insert(root->left, new_node);
    else if (root->data < new_node->data) root->right = BST_insert(root->right, new_node); 
    return root;
}

double sumNlevels_helper(BST_Node *root, int level, int cur_level) {
    if (root == NULL) {
        return 0.0;
    }
    // if (cur_level > level) { // do we need this? it depends
    //     return 0.0;
    // }
    if (cur_level == level) {
        return root->data;
    }
    // still need work -- USE RECURSION
    return root->data + sumNlevels_helper(root->left, level, cur_level + 1) + sumNlevels_helper(root->right, level, cur_level + 1);
}

/* Works on a BST that contains floating point values. Computes and returns the sum of all 
    entries in the BST that occupy nodes between the root and level K (where root is at level 0, 
    so if K is 3, it adds up any entries in nodes within the first 4 levels of the tree).
*/
double sum_Nlevels(BST_Node *root, int level) {
    // if (level < 0) return 0.0;
    // return sumNlevels_helper(root, level, 0);
    if (root == NULL) {
        return 0.0;
    }
    if (level < 0) {
        return 0.0;
    }
    if (level == 0) {
        return root->data;
    }
    // level > 0
    return root->data + sum_Nlevels(root->left, level - 1) + sum_Nlevels(root->right, level - 1);
}

int main() {
        //                            TREE:
        //                             50                      LEVEL 0
        //                 45                       85         LEVEL 1   
        //         38            49            72       92     LEVEL 2
        // 10          40                 69                   LEVEL 3
        //     12                                              LEVEL 4

    BST_Node *n = new_BST_Node(50.0);
    n = BST_insert(n, n);

    BST_Node *a = new_BST_Node(45.0);
    n = BST_insert(n, a);

    a = new_BST_Node(49.0);
    n = BST_insert(n, a);

    a = new_BST_Node(85.0);
    n = BST_insert(n, a);

    a = new_BST_Node(38.0);
    n = BST_insert(n, a);
        
    a = new_BST_Node(40.0);
    n = BST_insert(n, a);
   
    a = new_BST_Node(10.0);
    n = BST_insert(n, a);
        
    a = new_BST_Node(12.0);
    n = BST_insert(n, a);

    a = new_BST_Node(72.0);
    n = BST_insert(n, a);

    a = new_BST_Node(92.0);
    n = BST_insert(n, a);
    
    a = new_BST_Node(69.0);
    n = BST_insert(n, a);

    double sumK = sum_Nlevels(n, 0);
    printf("actual=%f, expected=50\n", sumK);

    sumK = sum_Nlevels(n, 1);
    printf("actual=%f, expected=180\n", sumK);

    sumK = sum_Nlevels(n, 2);
    printf("actual=%f, expected=431\n", sumK);

    sumK = sum_Nlevels(n, 3);
    printf("actual=%f, expected=550\n", sumK);

    sumK = sum_Nlevels(n, 4);
    printf("actual=%f, expected=562\n", sumK);

    sumK = sum_Nlevels(n, 5); // bad input? don't want to crash though!
    printf("actual=%f, expected=562\n", sumK);

    sumK = sum_Nlevels(n, -1); // bad input? don't want to crash though!
    printf("actual=%f, expected=0.0\n", sumK);
    
    // Suppose we pass on some BST to this function and find out that it doesn't return the correct sum.
    // How do we trace it to figure out where this happens?
    // However this is done (either with their preferred debug tool, or with print statements), they need to have access to:
    // The sequence order for each call in the recursion (recursion depth, level, or whatever you want to call this)
    //  - Which subproblem the recursion is working on
    //    - Any partial information the function has to work with (argument passed into the function, if any)
    //    - The actual data this recursive call will work with (e.g. if it's adding, what is it adding at this level? 
    //         is it looking in the right place?)
    //    - Any values returned from recursive calls made at this level
    //    - And the value it's going to return to the parent call

    return 0;
}