Sort array with repeated element using AVL Tree

/*
    C program for
    Sort array with repeated element using AVL Tree
*/
#include <stdio.h>
#include <stdlib.h>

// Avl tree node
struct TreeNode
{
	// Data value of tree
	int key;
	// Used to hold the height of current node
	int height;
	// Count occurrence nodes
	int occurrence;
	// Indicate left and right subtree
	struct TreeNode *left;
	struct TreeNode *right;
};
struct AVLTree
{
	struct TreeNode *root;
};
// Create new tree
struct AVLTree *newTree()
{
	// Create dynamic node
	struct AVLTree *tree = (struct AVLTree *)
	malloc(sizeof(struct AVLTree));
	if (tree != NULL)
	{
		tree->root = NULL;
	}
	else
	{
		printf("Memory Overflow to Create Tree\n");
	}
	// Return new tree
	return tree;
}
// Get the height of given node
int height(struct TreeNode *node)
{
	if (node == NULL)
	{
		return 0;
	}
	return node->height;
}
// Get the max value of given two numbers
int maxHeight(int a, int b)
{
	if (a > b)
	{
		return a;
	}
	else
	{
		return b;
	}
}
// Create a new Avl Tree node
struct TreeNode *newTreeNode(int key)
{
	// Create a tree node
	struct TreeNode *node = (struct TreeNode *) 
  							malloc(sizeof(struct TreeNode));
	if (node != NULL)
	{
		// Set initial node values
		node->key = key;
		node->height = 1;
		node->left = NULL;
		node->right = NULL;
		node->occurrence = 1;
	}
	else
	{
		printf("\nMemory overflow");
	}
	return node;
}
// Perform the Right rotate operation
struct TreeNode *rightRotate(struct TreeNode *node)
{
	// Get left child node
	struct TreeNode *left_node = node->left;
	// Get left node right subtree
	struct TreeNode *right_subtree = left_node->right;
	// update the left and right subtree 
	left_node->right = node;
	node->left = right_subtree;
	// Change the height of modified node
	node->height = maxHeight(height(node->left), 
                             height(node->right)) + 1;
	left_node->height = maxHeight(height(left_node->left), 
                                  height(left_node->right)) + 1;
	return left_node;
}
// Perform the Left Rotate operation
struct TreeNode *left_rotate(struct TreeNode *node)
{
	// Get right child node
	struct TreeNode *right_node = node->right;
	// Get right node left subtree
	struct TreeNode *left_subtree = right_node->left;
	// Update the left and right subtree 
	right_node->left = node;
	node->right = left_subtree;
	// Change the height of modified node
	node->height = maxHeight(height(node->left), 
                             height(node->right)) + 1;
	right_node->height = maxHeight(height(right_node->left), 
                                   height(right_node->right)) + 1;
	return right_node;
}
// Get the balance factor
int getBalanceFactor(struct TreeNode *node)
{
	if (node == NULL)
	{
		return 0;
	}
	return height(node->left) - height(node->right);
}
// Recursively, add a node in AVL tree
// Duplicate keys (key) are allowed
struct TreeNode *addElement(struct TreeNode *node, int key)
{
	if (node == NULL)
	{
		// return a new node
		return newTreeNode(key);
	}
	if (key < node->key)
	{
		node->left = addElement(node->left, key);
	}
	else if (key > node->key)
	{
		node->right = addElement(node->right, key);
	}
	else
	{
		node->occurrence = node->occurrence + 1;
		// When given key key already exists
		return node;
	}
	// Change the height of current node
	node->height = 1 + maxHeight(height(node->left), 
                                 height(node->right));
	// Get balance factor of a node
	int balance_factor = getBalanceFactor(node);
	// RR Case
	if (balance_factor > 1 && key < node->left->key)
	{
		return rightRotate(node);
	}
	// LL Case 
	if (balance_factor < -1 && key > node->right->key)
	{
		return left_rotate(node);
	}
	// LR Case
	if (balance_factor > 1 && key > node->left->key)
	{
		node->left = left_rotate(node->left);
		return rightRotate(node);
	}
	// RL Case 
	if (balance_factor < -1 && key < node->right->key)
	{
		node->right = rightRotate(node->right);
		return left_rotate(node);
	}
	return node;
}
// Display given array elements
void printRecord(int arr[], int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("  %d", arr[i]);
	}
}
// Collect sorted elements
void sortedElements(struct TreeNode *node, int arr[], int *index)
{
	if (node != NULL)
	{
      	// Visit left subtree
		sortedElements(node->left, arr, index);
		int i = 0;
		
		while (i < node->occurrence)
		{
			arr[ *index] = node->key;
            *index = *index + 1;
			i++;
		}
      	// Visit right subtree
		sortedElements(node->right, arr, index);
	}
}
void sort(int arr[], int n)
{
	// New Tree
	struct AVLTree *tree = newTree();
	for (int i = 0; i < n; ++i)
	{
		tree->root = addElement(tree->root, arr[i]);
	}
	int index = 0;
	sortedElements(tree->root, arr, & index);
}
int main(int argc, char const *argv[])
{
	// Array of integer elements
	int arr[] = {
		6 , 2 , 6 , 2 , 4 , 6 , 3 , 6 , 
        2 , 2 , 8 , 9 , 3 , 6 , 8 , 9
	};
	// Get the number of elements
	int n = sizeof(arr) / sizeof(arr[0]);
	sort(arr, n);
	printRecord(arr, n);
	return 0;
}

Output

  2  2  2  2  3  3  4  6  6  6  6  6  8  8  9  9