# AVL Tree Insert

• 12-06-2012
sakura
AVL Tree Insert
okay. So I have this code for AVL tree that works fine!

Code:

```#include<stdio.h> #include<stdlib.h> typedef struct node {     int *key;     struct node *left;     struct node *right;     int height; }node ,*nodeptr;  int CompareIntegerDefault(int *data1,int * data2) {                 if(*data1>*data2)                 return (1);         else if(*data1==*data2)                 return (0);         else                 return (-1); } // A utility function to get maximum of two integers int max1(int a, int b);   // A utility function to get height of the tree int height(struct node *N) {     if (N == NULL)         return 0;     return N->height; }   // A utility function to get maximum of two integers int max1(int a, int b) {         if(a>b)                 return a;         else                 return b;   // return (a > b)? a : b; }   /* Helper function that allocates a new node with the given key and     NULL left and right pointers. */ struct node* newNode(int *key) {     struct node* node = (struct node*)                         malloc(sizeof(struct node));     node->key  = key;     node->left  = NULL;     node->right  = NULL;     node->height = 1;  // new node is initially added at leaf     return(node); } typedef struct ContainerHandle {         struct node * root;         }ContainerHandle;   // A utility function to right rotate subtree rooted with y // See the diagram given above. struct node *rightRotate(struct node *y) {     struct node *x = y->left;     struct node *T2 = x->right;       // Perform rotation     x->right = y;     y->left = T2;       // Update heights     y->height = max1(height(y->left), height(y->right))+1;     x->height = max1(height(x->left), height(x->right))+1;       // Return new root     return x; }   // A utility function to left rotate subtree rooted with x // See the diagram given above. struct node *leftRotate(struct node *x) {     struct node *y = x->right;     struct node *T2 = y->left;       // Perform rotation     y->left = x;     x->right = T2;       //  Update heights     x->height = max1(height(x->left), height(x->right))+1;     y->height = max1(height(y->left), height(y->right))+1;       // Return new root     return y; }   // Get Balance factor of node N int getBalance(struct node *N) {     if (N == NULL)         return 0;     return height(N->left) - height(N->right); }   struct node* insert(struct node* node, void *key) {     /* 1.  Perform the normal BST rotation */     int balance;         if (node == NULL)         return(newNode(key));       if (CompareIntegerDefault(key , node->key)<0)         node->left  = insert(node->left, key);     else         node->right = insert(node->right, key);       /* 2. Update height of this ancestor node */     node->height = max1(height(node->left), height(node->right)) + 1;       /* 3. Get the balance factor of this ancestor node to check whether       this node became unbalanced */     balance = getBalance(node);       // If this node becomes unbalanced, then there are 4 cases       // Left Left Case     if (balance > 1 && CompareIntegerDefault(key , node->left->key)<0)         return rightRotate(node);       // Right Right Case     if (balance < -1 && CompareIntegerDefault(key , node->right->key)>0)         return leftRotate(node);       // Left Right Case     if (balance > 1 && CompareIntegerDefault(key , node->left->key)>0)     {         node->left =  leftRotate(node->left);         return rightRotate(node);     }       // Right Left Case     if (balance < -1 && CompareIntegerDefault(key , node->right->key)<0)     {         node->right = rightRotate(node->right);         return leftRotate(node);     }       /* return the (unchanged) node pointer */     return node; } void preOrder(struct node *root) {     if(root != NULL)     {         printf("%d ",*(int *)(root->key));         preOrder(root->left);         preOrder(root->right);     } } int main() {         ContainerHandle *hdl;     /* Constructing tree given in the above figure */         int a,b,c,d,e,f,g,i,j,k,l,m,n,o,p,q,r,s,t;     hdl=(ContainerHandle *)malloc(sizeof(ContainerHandle));           hdl->root=NULL;         a=9;         hdl->root=insert(hdl->root, &a);         b=5;     hdl->root=insert(hdl->root, &b);     c=10;         hdl->root=insert(hdl->root, &c);     d=0;         hdl->root=insert(hdl->root, &d);     e=6;         hdl->root=insert(hdl->root, &e);     f=11;         hdl->root=insert(hdl->root, &f);     g=-1;         hdl->root=insert(hdl->root, &g);     i=1;         hdl->root=insert(hdl->root, &i);     j=2;         hdl->root=insert(hdl->root, &j);       /* The constructed AVL Tree would be             9           /  \           1    10         /  \    \       0    5    11       /    /  \     -1  2    6     */       printf("Pre order traversal of the constructed AVL tree is \n");     preOrder(hdl->root);             return 0; }```
but I dont want the insert function to return a structure pointer( since I'm planning to make it return error codes.

so I did this

Code:

```#include<stdio.h> #include<stdlib.h> typedef struct node {     int *key;     struct node *left;     struct node *right;     int height; }node ,*nodeptr;  int CompareIntegerDefault(int *data1,int * data2) {                 if(*data1>*data2)                 return (1);         else if(*data1==*data2)                 return (0);         else                 return (-1); } // A utility function to get maximum of two integers int max1(int a, int b);   // A utility function to get height of the tree int height(struct node *N) {     if (N == NULL)         return 0;     return N->height; }   // A utility function to get maximum of two integers int max1(int a, int b) {         if(a>b)                 return a;         else                 return b;   // return (a > b)? a : b; }   /* Helper function that allocates a new node with the given key and     NULL left and right pointers. */ struct node* newNode(int *key) {     struct node* node = (struct node*)                         malloc(sizeof(struct node));     node->key  = key;     node->left  = NULL;     node->right  = NULL;     node->height = 1;  // new node is initially added at leaf     return(node); } typedef struct ContainerHandle {         struct node * root;         }ContainerHandle;   // A utility function to right rotate subtree rooted with y // See the diagram given above. struct node *rightRotate(struct node *y) {     struct node *x = y->left;     struct node *T2 = x->right;       // Perform rotation     x->right = y;     y->left = T2;       // Update heights     y->height = max1(height(y->left), height(y->right))+1;     x->height = max1(height(x->left), height(x->right))+1;       // Return new root     return x; }   // A utility function to left rotate subtree rooted with x // See the diagram given above. struct node *leftRotate(struct node *x) {     struct node *y = x->right;     struct node *T2 = y->left;       // Perform rotation     y->left = x;     x->right = T2;       //  Update heights     x->height = max1(height(x->left), height(x->right))+1;     y->height = max1(height(y->left), height(y->right))+1;       // Return new root     return y; }   // Get Balance factor of node N int getBalance(struct node *N) {     if (N == NULL)         return 0;     return height(N->left) - height(N->right); }   void insert(struct node** node, void *key) {     /* 1.  Perform the normal BST rotation */     int balance;         if ((*node) == NULL)         (*node)=newNode(key);       if (CompareIntegerDefault(key , (*node)->key)<0)         insert(&((*node)->left), key);     else         insert(&((*node)->right), key);       /* 2. Update height of this ancestor (*node) */     (*node)->height = max1(height((*node)->left), height((*node)->right)) + 1;       /* 3. Get the balance factor of this ancestor (*node) to check whether       this (*node) became unbalanced */     balance = getBalance((*node));       // If this (*node) becomes unbalanced, then there are 4 cases       // Left Left Case     if (balance > 1 && CompareIntegerDefault(key , (*node)->left->key)<0)         (*node)= rightRotate((*node));       // Right Right Case     if (balance < -1 && CompareIntegerDefault(key , (*node)->right->key)>0)         (*node)= leftRotate((*node));       // Left Right Case     if (balance > 1 && CompareIntegerDefault(key , (*node)->left->key)>0)     {         (*node)->left =  leftRotate((*node)->left);         (*node)= rightRotate((*node));     }       // Right Left Case     if (balance < -1 && CompareIntegerDefault(key , (*node)->right->key)<0)     {         (*node)->right = rightRotate((*node)->right);         (*node)= leftRotate((*node));     }       /* return the (unchanged) (*node) pointer */   } void preOrder(struct node *root) {     if(root != NULL)     {         printf("%d ",*(int *)(root->key));         preOrder(root->left);         preOrder(root->right);     } } int main() {         ContainerHandle *hdl;     /* Constructing tree given in the above figure */         int a,b,c,d,e,f,g,i,j,k,l,m,n,o,p,q,r,s,t;     hdl=(ContainerHandle *)malloc(sizeof(ContainerHandle));           hdl->root=NULL;         a=9;         insert(&(hdl->root), &a);         b=5;     insert(&(hdl->root), &b);     c=10;         insert(&(hdl->root), &c);     d=0;         insert(&(hdl->root), &d);     e=6;         insert(&(hdl->root), &e);     f=11;         insert(&(hdl->root), &f);     g=-1;         insert(&(hdl->root), &g);     i=1;         insert(&(hdl->root), &i);     j=2;         insert(&(hdl->root), &j);       /* The constructed AVL Tree would be             9           /  \           1    10         /  \    \       0    5    11       /    /  \     -1  2    6     */       printf("Pre order traversal of the constructed AVL tree is \n");     preOrder(hdl->root);             return 0; }```
I get a warning:-

warning C4717: 'insert' : recursive on all control paths, function will cause runtime stack overflow.
I can't figure out why this doesn't work!!
• 12-06-2012
Salem
> if (balance > 1 && max1(*key , *((*node)->left->key))<0)
max1 doesn't return <0 or >0 or anything like that.
It's just the larger of the two numbers, not the comparison of the two numbers.

You also make use of max() as well.
Perhaps you need to clean up the code by giving one of them a much better name.

> struct node* insert(struct node** node, int *key)
Make this
void insert(struct node** node, int *key)
since you never actually return a node, nor do you ever assign the result (even if it did).
• 12-06-2012
sakura
Okay the code was messed up, but has been editted now. Problem persists. Please help me out!!!
• 12-07-2012
Salem
> warning C4717: 'insert' : recursive on all control paths, function will cause runtime stack overflow.
> I can't figure out why this doesn't work!!
Do you know what the word "all" means?

Can you see that calling insert() ALWAYS calls insert(), so you have recursion without end?

Perhaps something like this
Code:

```    if ((*node) == NULL) {         (*node)=newNode(key);     } else if (CompareIntegerDefault(key , (*node)->key)<0) {         insert(&((*node)->left), key);     } else {         insert(&((*node)->right), key);     }```
where the simple case does NOT call insert recursively.