AVLTree

AVLTree.c

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

typedef struct _node node;
struct _node {
    node *head;
    node *left;
    node *right;
    int value;
    int height;
};

int height(node *p) {
    return p ? p->height : -1;
}

int balanceFactor(node *p) {
    return height(p->left) - height(p->right);
}

void rotateLeft(node **p) {
    node *prevHead = (*p)->head;
    (*p)->head = (*p)->right;
    (*p)->right = (*p)->head->left;
    (*p)->head->left = (*p);
    (*p)->head->head = prevHead;
    *p = (*p)->head;
}

void rotateRight(node **p) {
    node *prevHead = (*p)->head;
    (*p)->head = (*p)->left;
    (*p)->left = (*p)->head->right;
    (*p)->head->right = (*p);
    (*p)->head->head = prevHead;
    *p = (*p)->head;
}

void insert(node *head, node **root, int value) {
    if (*root == NULL) {
        *root = (node *)malloc(sizeof(node));
        (*root)->left = NULL;
        (*root)->right = NULL;
        (*root)->head = head;
        (*root)->value = value;
        (*root)->height = 0;
        return;
    }
    if (value < (*root)->value) {
        insert(*root, &(*root)->left, value);
        (*root)->height = height((*root)->left) + 1;
        if (balanceFactor(*root) == 2) {
            node **temp = &(*root)->left;
            if (balanceFactor(*temp) == -1) {
                rotateLeft(temp);
            }
            rotateRight(root);
        }
    }
    else {
        insert(*root, &(*root)->right, value);
        (*root)->height = height((*root)->right) + 1;
        if (balanceFactor(*root) == -2) {
            node **temp = &(*root)->right;
            if (balanceFactor(*temp) == 1) {
                rotateRight(temp);
            }
            rotateLeft(root);
        }
    }
}

void inOrder(node *p) {
    if (p) {
        inOrder(p->left);
        printf("%d ", p->value);
        inOrder(p->right);
    }
}

void preOrder(node *p) {
    if (p) {
        printf("%d ", p->value);
        inOrder(p->left);
        inOrder(p->right);
    }
}

void postOrder(node *p) {
    if (p) {
        inOrder(p->left);
        inOrder(p->right);
        printf("%d ", p->value);
    }
}

int main() {
    node *AVLTree = NULL;
    int n, i, d;
    printf("Enter number of nodes followed by their values:\n");
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &d);
        insert(AVLTree, &AVLTree, d);
    }
    printf("InOrder Traversal:\t");
    inOrder(AVLTree);
    printf("\n");
    printf("PreOrder Traversal:\t");
    preOrder(AVLTree);
    printf("\n");
    printf("PostOrder Traversal:\t");
    postOrder(AVLTree);
    printf("\n");
    return 0;
}