c - Placing a new node into the next available position in a binary tree heap? -

let's have data structure minimum heap:

struct node{     int height;     struct node *parent;     struct node *left;     struct node *right; };   

what want add new node next available position (keeping min heap property not matter @ point.) have far in case of empty tree (the root instantiated earlier null earlier in code). having trouble figuring out logic in case root exists. need add elements in 1 one. understand how using heap array, need using heap binary tree.

void insert(int number) {     struct node *nodetoinsert;     nodetoinsert=(struct node*)malloc(sizeof(struct node));     nodetoinsert->value = number;      if(root == null)     {         root = nodetoinsert;         root->left = null;         root->right = null;     } } 

if understand correctly, want know how descend complete binary tree insert next node. need know how many nodes in bottom level. bits of number tell how turn (left or right) move down tree next available position. happliy, can number of nodes in bottom level total number of items in tree, want track anyway.

// let n current number of nodes in tree. // subtract sizes of levels until we're @ last. (ls = 1, n_levels = 0; ; ls *= 2, n_levels++) {   if (n - ls < 0) break;   n -= ls; } // n contains number of nodes in bottom level // n_levels contains number of complete levels above. struct node *p = root; (bit = 1 << (n_levels - 1); bit != 1; bit >>= 1)   if (n & bit)     p = p->right;   else     p = p->left; if (n & 1)   p->right = new_node(); else   p->left = new_node(); 

for example n = 10. have perfect tree of 7 nodes plus 3 on lowest, incomplete level. first loop subtracts 1, 2, 4, finishes n = 3 = 011_2 , n_levels = 3. consequently, second loop creates bit mask 1 << 2 = 4 = 100_2. loop therefore moves down tree p = p->left high order bit 0 of n, p = p->right 1. final bit 1, therefore puts new node @ p->right. correct place (11) can see in picture:

        === 1 ---       //         \       2           3     /  \\       /   \    4     5     6     7   / \   / \\  8   9 10  11  

note pseudocode above not handle n=0 case, code that.