Please add one function to this code to get this:

The tree has 300000 leaves

I got this output I just need to add the total leaves.

depth: 13 14 15 16 17 18 19 20 21 22 23 count: 9 168 1798 11113 36291 67735 79899 62443 31144 8576 824

Here is the code

#include  #include  #define BLOCKSIZE 256 typedef int object_t; typedef int key_t; typedef struct tr_n_t { key_t key; struct tr_n_t *left; struct tr_n_t *right; int height; } tree_node_t; tree_node_t *currentblock = NULL; int size_left; tree_node_t *free_list = NULL; tree_node_t *get_node() { tree_node_t *tmp; if( free_list != NULL ) { tmp = free_list; free_list = free_list -> left; } else  { if( currentblock == NULL || size_left == 0) { currentblock = (tree_node_t *) malloc( BLOCKSIZE * sizeof(tree_node_t) ); size_left = BLOCKSIZE; } tmp = currentblock++; size_left -= 1; } return( tmp ); } void return_node(tree_node_t *node) { node->left = free_list; free_list = node; } tree_node_t *create_tree(void) { tree_node_t *tmp_node; tmp_node = get_node(); tmp_node->left = NULL; return( tmp_node ); } void left_rotation(tree_node_t *n) { tree_node_t *tmp_node; key_t tmp_key; tmp_node = n->left; tmp_key = n->key; n->left = n->right; n->key = n->right->key; n->right = n->left->right; n->left->right = n->left->left; n->left->left = tmp_node; n->left->key = tmp_key; } void right_rotation(tree_node_t *n) { tree_node_t *tmp_node; key_t tmp_key; tmp_node = n->right; tmp_key = n->key; n->right = n->left; n->key = n->left->key; n->left = n->right->left; n->right->left = n->right->right; n->right->right = tmp_node; n->right->key = tmp_key; } object_t *find(tree_node_t *tree, key_t query_key) { tree_node_t *tmp_node; if( tree->left == NULL ) return(NULL); else  { tmp_node = tree; while( tmp_node->right != NULL ) { if( query_key < tmp_node->key ) tmp_node = tmp_node->left; else  tmp_node = tmp_node->right; } if( tmp_node->key == query_key ) return( (object_t *) tmp_node->left ); else  return( NULL ); } } int insert(tree_node_t *tree, key_t new_key, object_t *new_object) { tree_node_t *tmp_node; int finished; if( tree->left == NULL ) { tree->left = (tree_node_t *) new_object; tree->key = new_key; tree->height = 0; tree->right = NULL; } else  { tree_node_t * path_stack[100]; int path_st_p = 0; tmp_node = tree; while( tmp_node->right != NULL ) { path_stack[path_st_p++] = tmp_node; if( new_key < tmp_node->key ) tmp_node = tmp_node->left; else  tmp_node = tmp_node->right; } /* found the candidate leaf. Test whether key distinct */ if( tmp_node->key == new_key ) return( -1 ); /* key is distinct, now perform the insert */ { tree_node_t *old_leaf, *new_leaf; old_leaf = get_node(); old_leaf->left = tmp_node->left; old_leaf->key = tmp_node->key; old_leaf->right = NULL; old_leaf->height = 0; new_leaf = get_node(); new_leaf->left = (tree_node_t *) new_object; new_leaf->key = new_key; new_leaf->right = NULL; new_leaf->height = 0; if( tmp_node->key < new_key ) { tmp_node->left = old_leaf; tmp_node->right = new_leaf; tmp_node->key = new_key; } else  { tmp_node->left = new_leaf; tmp_node->right = old_leaf; } tmp_node->height = 1; } /* rebalance */ finished = 0; while( path_st_p > 0 && !finished ) { int tmp_height, old_height; tmp_node = path_stack[--path_st_p]; old_height= tmp_node->height; if( tmp_node->left->height - tmp_node->right->height == 2 ) { if( tmp_node->left->left->height - tmp_node->right->height == 1 ) { right_rotation( tmp_node ); tmp_node->right->height = tmp_node->right->left->height + 1; tmp_node->height = tmp_node->right->height + 1; } else  { left_rotation( tmp_node->left ); right_rotation( tmp_node ); tmp_height = tmp_node->left->left->height; tmp_node->left->height = tmp_height + 1; tmp_node->right->height = tmp_height + 1; tmp_node->height = tmp_height + 2; } } else if ( tmp_node->left->height - tmp_node->right->height == -2 ) { if( tmp_node->right->right->height - tmp_node->left->height == 1 ) { left_rotation( tmp_node ); tmp_node->left->height = tmp_node->left->right->height + 1; tmp_node->height = tmp_node->left->height + 1; } else  { right_rotation( tmp_node->right ); left_rotation( tmp_node ); tmp_height = tmp_node->right->right->height; tmp_node->left->height = tmp_height + 1; tmp_node->right->height = tmp_height + 1; tmp_node->height = tmp_height + 2; } } else /* update height even if there was no rotation */ { if( tmp_node->left->height > tmp_node->right->height ) tmp_node->height = tmp_node->left->height + 1; else  tmp_node->height = tmp_node->right->height + 1; } if( tmp_node->height == old_height ) finished = 1; } } return( 0 ); } //Please read this. //THIS IS THE FUNCTION THAT I ADDED. PLEASE FIX ONLY THIS FUNCTIONS. DO NOT TOUCH THE REST OF THE CODE. THAT THE CODE THA IS NOT ALLOWED TO MODIFY. int getHeight(tree_node_t *tree) { // do not change this prototype function name. This function name has to stay the same. // if the current node is NULL if (tree == NULL) return -1; // this is because the height of a leaf node is zero. So the height of a NULL must be 1 less else { // getting the left subtree height int l = getHeight(tree->left); // getting the right subtree height int r = getHeight(tree->right); // return the larger height if (l > r) return(l + 1); return(r + 1); } } void getLevel(tree_node_t *tree, int myheight, int totalheight, int count[]) { if (tree == NULL) return; int level = totalheight - myheight; if(tree->left == NULL && tree->right == NULL) // it is a leaf, so the distribution count should be increased count[level] ++; // For the recursive call, the totalheight will remain the same, but the height of the node is one less than current one if(tree->left != NULL) getLevel(tree->left, myheight - 1, totalheight, count); if(tree->right != NULL) getLevel(tree->right, myheight - 1, totalheight, count); } void depth_distribution(tree_node_t *tree) { if(tree == NULL) return; int height = tree->height; // The height is already updated during insertion int i; int count[100]; // This array will recursively be passed for all leafs and updated accordingly for(i = 0; i <= height; i++) count[i] = 0; // Initialize to zero before making the call for calculating leafs at each level getLevel(tree, height + 1, height, count); printf("depth: "); for (i = 0 ; i <= height; i++) { if(count[i]) //print only non -zero values printf("%d ", i); } printf(" count: "); for (i = 0; i <= height; i++) { if(count[i]) printf("%d ", count[i]); } printf(" "); } //ALSO NOT MAIN AS WELL. NOT ALLOWED TO MODIFY MAIN FUNCTION. int main() { tree_node_t *searchtree; char nextop; int i; int * insobj; searchtree = create_tree(); insobj = (int *) malloc(sizeof(int)); *insobj = 654321; printf("Made Tree: Height-Balanced Tree "); for(i=0; i<100000; i++) { insert(searchtree, i, insobj); insert(searchtree, i+200000, insobj); insert(searchtree, 400000-i, insobj); } depth_distribution(searchtree); return(0); }