Simple AVL Tree Insert

avl-tree.c

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

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

typedef struct {
	struct node *root;
} Tree;

int maxHeight(Node *a, Node *b) {
	int weightA = (a == NULL)? 0 : a->height;
	int weightB = (b == NULL)? 0 : b->height;
	return (weightA > weightB)? weightA : weightB;
}

int determineBalance(Node *node) {
	if (node != NULL) {
		int leftWeight = (node->left == NULL)? 0 : node->left->height;
		int rightWeight = (node->right == NULL)? 0 : node->right->height;

		return leftWeight - rightWeight;
	}
	return 0;
}

Node *newNode(int value) {
	Node *node = (Node *)malloc(sizeof(Node *));
	node->value = value;
	node->height = 1;
	node->left = NULL;
	node->right = NULL;
	return node;
}

Node *rotateRight(Node *node) {
	Node *oldLeft = node->left;
	Node *temp = oldLeft->right;

	oldLeft->right = node;
	node->left = temp;

	node->height = maxHeight(node->left, node->right) + 1;
	oldLeft->height = maxHeight(oldLeft->left, oldLeft->right) + 1;

	return oldLeft;
}

Node *rotateLeft(Node *node) {
	Node *oldRight = node->right;
	Node *temp = oldRight->left;

	oldRight->left = node;
	node->right = temp;

	node->height = maxHeight(node->left, node->right) + 1;
	oldRight->height = maxHeight(oldRight->left, oldRight->right) + 1;

	return oldRight;
}

Node *insert(Node *node, int value) {
	int balance;

	if (node == NULL) {
		return newNode(value);
	}

	if (value < node->value) {
		node->left = insert(node->left, value);
	} else if (value > node->value) {
		node->right = insert(node->right, value);
	} else {
		return node;
	}

	// TREE BALANCING PART //
	node->height = 1 + maxHeight(node->left, node->right);
	balance = determineBalance(node);

	if ((balance > 1) && (value < node->left->value)) {
		return rotateRight(node);
	}

	if ((balance < -1) && (value > node->right->value)) {
		return rotateLeft(node);
	}

	if ((balance > 1) && (value > node->left->value)) {
		node->left = rotateLeft(node->left);
		return rotateRight(node);
	}

	if ((balance < -1) && (value < node->right->value)) {
		node->right = rotateRight(node->right);
		return rotateLeft(node);
	}

	return node;
}

void printNode(Node *node) {
	if (node != NULL) {
		printf("%d", node->value);
		if (node->left != NULL || node->right != NULL) {
			printf("(");
			printNode(node->left);
			if (node->left != NULL && node->right) {
				printf(",");
			}
			printNode(node->right);
			printf(")");
		}
	}
}

Tree *newTree() {
	Tree *tree = (Tree *)malloc(sizeof(Tree *));
	tree->root = NULL;

	return tree;
}

void insertToTree(Tree *tree, int value) {
	tree->root = insert(tree->root, value);
}

void printTree(Tree *tree) {
	printNode(tree->root);
    printf("\n");
}

int main() {
	Tree *tree = newTree();
	insertToTree(tree, 1);
	insertToTree(tree, 2);
	insertToTree(tree, 3);
	insertToTree(tree, 4);
	insertToTree(tree, 5);
	insertToTree(tree, 6);
	insertToTree(tree, 7);

	printTree(tree); // -> 4(2(1,3),6(5,7))
	return 0;
}

runner.sh

gcc -o avl-tree.bin avl-tree.c && ./avl-tree.bin