Adding additional elements in a binary tree without changing the height of a tree

Question

I'm having a bit of a problem getting this to understand so I'll ask here, I only got good answers here.

The task is : It is necessary to write a new function that (and calculated) lists how many elements can be entered into the tree without having to increase his height. The function outputs only and explicitly numerical value ex. 17/n.

Can somebody clarify?

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

#define MAX_TREE_STRING 100
#define MAX_NODES 100

// width and height of 2D array used for function print_tree
#define WIDTH 80
#define HEIGHT 10

typedef struct node {
    int key;
    struct node *left; 
    struct node *right;
}Node;

int print_tree(Node *tree, int is_left, int offset, int depth, char s[HEIGHT][WIDTH]) {
    char b[HEIGHT];
    int i, left, right, width = 3;

    if (!tree) return 0;
    sprintf(b,"(%c)",tree->key);
    left = print_tree(tree->left,1,offset,depth+1,s);
    right = print_tree(tree->right,0,offset+left+width,depth+1,s);
    for (i=0; i<width; i++)
        s[depth][offset+left+i] = b[i];
    if (depth) {
        if (is_left) {
            for (i=0; i<width+right; i++)
                s[depth-1][offset+left+width/2+i] = '-';
        } else {
            for (i=0; i<left+width; i++)
                s[depth-1][offset-width/2+i] = '-';
        }
        s[depth-1][offset+left+width/2] = '.';
    }
    return left+width+right;
}

Node *create_tree(char *tree_string) {
    Node *queue[MAX_NODES];
    Node *trenutni, *parent;
    int tail, head, i;

    tail = head = -1;
    trenutni = parent = NULL;

    for(i=0; i<strlen(tree_string); i++) {
        if (tree_string[i]!=';') {
            if (tree_string[i]=='-') continue;
            trenutni = (Node *)malloc(sizeof(Node));
            trenutni->key = tree_string[i];
            trenutni->left = trenutni->right = NULL;

            queue[++tail] = trenutni;
            if (parent && tree_string[i-1]==';') {
                parent->left = trenutni;
            } else if (i>0) {
                parent->right = trenutni;
            }
        } else {
            parent = queue[++head];
        }
    }
    return queue[0];
}

/*
void function_name(arguments) {
}
*/

int main () {
    Node *root=NULL;
    int i, menu_choice;
    char c, tree_string[MAX_TREE_STRING];
    char print_format[6], empty_line[WIDTH], s[HEIGHT][WIDTH];

    setbuf(stdout, NULL);
    do {
        menu_choice = 0;
        //printf("\n1 Description of a function (function_name)");
        printf("\n2 Create tree \n3 Print \n4 Exit\n");
        scanf("%d", &menu_choice);
        switch (menu_choice) {
            case 1:
                //function_name(arguments);
                break;
            case 2:
                printf("Create a tree as queue of alphanumeric entries separated with ;\n");
                scanf(" %s", tree_string);
                root = create_tree(tree_string);
                break;
            case 3:
                sprintf(print_format, "%%%ds", WIDTH-1);
                for (i=0; i<HEIGHT; i++) 
                    sprintf(s[i], print_format, " ");

                print_tree(root,0,0,0,s);

                sprintf(empty_line, print_format, " ");
                for (i=0; i<HEIGHT; i++) {
                    if (strcmp(s[i],empty_line))
                        printf("%s\n", s[i]);
                }
                break;
            case 4:
                break;
            default:
                while((c = getchar()) != '\n' && c != EOF);
        }
    } while(menu_choice!=4);
    return 0;
}

Clarification: after you have inserted the elements into a tree, you have to find which is the biggest height of the tree and how much elements can you insert into other nodes of the tree, to the height of biggest and not crossing it over.

Answer 1

A full Binary tree contains 2^h -1 nodes. Thus, you can insert 2^h-1 - n more nodes without changing the height of the tree. (where n is the current number of nodes in the tree).