Node deletion in K dimensional tree

// C program for
// Node deletion in K dimensional tree  
#include <stdio.h>

#include <limits.h>

#include <stdlib.h>

// Define tree node
struct TreeNode
{
	int *keys;
	struct TreeNode *left;
	struct TreeNode *right;
};
struct KTree
{
	int k;
	struct TreeNode *root;
};
// Returns the new K Dimensional Tree
struct KTree *createTree(int k)
{
	struct KTree *tree = (struct KTree *) malloc(sizeof(struct KTree));
	if (tree != NULL)
	{
		tree->k = k;
		tree->root = NULL;
	}
	else
	{
		printf("\n Memory Overflow when create new Tree");
	}
}
// Creating and returning new node of tree
struct TreeNode *createNode(int data[], int k)
{
	struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
	if (node != NULL)
	{
		// Create memory of node key
		node->keys = (int *) malloc((sizeof(int)) *(2));
		node->left = NULL;
		node->right = NULL;
		for (int i = 0; i < k; i++)
		{
			node->keys[i] = data[i];
		}
	}
	else
	{
		printf("\n Memory Overflow when create new node Tree");
	}
	return node;
}
// Handles the request to add new node in Tree
void insert(struct KTree *tree, int data[])
{
	if (tree->root == NULL)
	{
		// When add first node of tree
		tree->root = createNode(data, tree->k);
	}
	else
	{
		struct TreeNode *auxiliary = tree->root;
		int depth = 0;
		int axis = 0;
		// Add new node in tree
		while (auxiliary != NULL)
		{
			axis = depth % tree->k;
			if (auxiliary->keys[axis] > data[axis])
			{
				if (auxiliary->left == NULL)
				{
					// Add new node
					auxiliary->left = createNode(data, tree->k);
					// break the loop
					auxiliary = NULL;
				}
				else
				{
					// visit left subtree
					auxiliary = auxiliary->left;
				}
			}
			else
			{
				if (auxiliary->right == NULL)
				{
					// Add new node
					auxiliary->right = createNode(data, tree->k);
					// break the loop
					auxiliary = NULL;
				}
				else
				{
					// visit right subtree
					auxiliary = auxiliary->right;
				}
			}
			depth++;
		}
	}
}
//  Print the all key of a given node
void printData(int data[], int k)
{
	printf(" (");
	for (int i = 0; i < k; ++i)
	{
		if (i > 0)
		{
			printf(" , %d", data[i]);
		}
		else
		{
			printf(" %d", data[i]);
		}
	}
	printf(")\n");
}
// Display tree node
void printTree(struct TreeNode *node, int k)
{
	if (node != NULL)
	{
		printTree(node->left, k);
		printData(node->keys, k);
		printTree(node->right, k);
	}
}

// Compare node and given point
int isEquals(int node[], int point[], int k)
{
    for (int i = 0; i < k; ++i)
    {
        if (node[i] != point[i])
        {
            return 0;
        }
    }
    //  When both are same
    return 1;
}

// return the minimum node by using of given dimension
struct TreeNode * minPoint( struct TreeNode *node1,
				struct TreeNode *node2, 
				int dim)
{
	if(node1==NULL)
	{
		// When node 1 empty
		return node2;
	}
	if(node2 == NULL)
	{
		// When node 2 empty
		return node1;
	}

	if(node1->keys[dim] < node2->keys[dim])
	{
		// Node 1 is smaller
		return node1;
	}
	// Node 2 is smaller
	return node2;

}
// Recursively finding the minimum of given dimension
struct TreeNode * findMinimum(struct TreeNode *node, int dim, int k, int depth)
{
	if (node == NULL)
	{
		// When get a null Node
		return NULL;
	}
	// Get dimension position
	int position = depth % k;

	if (position == dim)
	{
		// When position are equal to given a dimension
		if (node->left == NULL)
		{
			// Returns the current dimension
			return node;
		}

		
		return minPoint(node, 
				findMinimum(node->left, dim, k, depth + 1),dim);
	}
	// When position are equal to given a dimension
	// Then resultant node can be exists in left or right subtree
	return minPoint(node, 
			minPoint(findMinimum(node->left, dim, k, depth + 1), 
			findMinimum(node->right, dim, k, depth + 1),dim),dim);
}
// Handles the request of find minimum point using given dimensions
void minimum(struct KTree *tree, int dim)
{
	if (tree->root == NULL)
	{
		printf("\n Empty Tree");
	}
	else if (dim < 0 || dim + 1 > tree->k)
	{
		printf("\n Given dimensions are not valid ");
	}
	else
	{
		struct TreeNode*n = findMinimum(tree->root, dim, tree->k, 0);
		
		printf("\n Given Dimension : %d", dim);
		
		if(n != NULL)
		{
	
			printf("\n Minimum is : %d", n->keys[dim]);
		}

	}
}


// Copy node 2 value into node1
void copyData(int node1[], int node2[], int k) 
{ 
   for (int i=0; i < k; i++) 
   {
       node1[i] = node2[i]; 
   }
} 
  
// Handles the request of remove given point node in tree
struct TreeNode *removeNode(
	struct TreeNode *node, 
	int k, 
	int point[], 
	int depth) 
{ 
    
    if (node == NULL) 
    {
        return NULL; 
    }
  	
    int dim = depth % k; 
  

    if (isEquals(node->keys, point,k)) 
    { 
   		// When current node is same as deleted point
   		// Here are three possibility

        if (node->right != NULL) 
        { 
            // Case 1 : When right subtree not NULL
        	// Then find minimum node point and replace	by current node
            struct TreeNode *min = findMinimum(node->right, dim, k, 0); 

            // minimum point replace by current node
            copyData(node->keys, min->keys, k); 
  
    		// Recursively find new minimum deleted point
            node->right = removeNode(node->right,k, min->keys, depth+1); 
        } 
        else if (node->left != NULL) 
        { 
        	// Case 2 : When current node left subtree not Empty
        	// Then find minimum node point in left subtree and 
        	// replace by current node
            struct TreeNode *min = findMinimum(node->left, dim,k, 0); 

            // minimum point replace by current node
            copyData(node->keys, min->keys, k); 

            // Recursively find new minimum deleted point
            node->right = removeNode(node->left,k, min->keys, depth+1); 
        } 
        else 
        { 
        	// Case 3 :  When current node is leaf node
        	// Then remove it
            free(node); 
            return NULL; 
        } 
        return node; 
    } 
  
   	// Choose the left and right subtree by using given point
    if ( node->keys[dim] > point[dim] ) 
    {
        node->left = removeNode(node->left,k, point, depth+1); 
    }
    else
    {
        node->right = removeNode(node->right,k, point, depth+1); 
    }
    return node; 
} 
  
// Handles the request to delete given point in tree
void deleteNode(struct KTree *tree, int point[]) 
{ 

	if (tree->root == NULL)
	{
		printf("\n Empty Tree");
		return;
	}

	printf("\n Remove point \n");

	printData(point,tree->k);
	// Assuming that the given point length is equal to the tree node keys
    tree->root = removeNode(tree->root, tree->k, point, 0); 
} 
  

int main(int argc, char
	const *argv[])
{
	// Number of Dimensions
	int k = 2;
	struct KTree *tree = createTree(k);
	// 2d points
	int data[][2] = {
		{
			8 , 9
		},
		{
			7 , 6
		},
		{
			3 , 9
		},
		{
			11 , 12
		},
		{
			2 , 8
		},
		{
			9 , 4
		},
		{
			10 , 13
		},
		{
			14 , 8
		}
	};
	// Remove node points
	int point1[] = {7,6};
	int point2[] = {8,9};
	// Get the number of elements
	int n = sizeof(data) / sizeof(data[0]);
	// Insert all given nodes
	for (int i = 0; i < n; ++i)
	{
		insert(tree, data[i]);
	}
	printf("\n Before Delete Tree Nodes\n");
	/*
	     (8, 9)
	    /      \
	  (7,6)    (11,12)     
	     \      /    \
	     (3,9)(9,4)  (10,13)
		/        \
	  (2,8)      (14,8)          
	-----------------
	Developed tree
	*/
	// Print  tree elements in inorder  form
	printTree(tree->root, tree->k);

	// Case 1
	deleteNode(tree,point1);
	/*
	     (8, 9)
	    /      \
	  (2,8)    (11,12)     
	     \      /    \
	     (3,9)(9,4)  (10,13)
		         \
	  		      (14,8)          
	-----------------
		After Remove (7,6)
	*/
	printf("\n After Delete Tree Nodes\n");
	
	// Print  tree elements in inorder  form
	printTree(tree->root, tree->k);

	// Case 2
	deleteNode(tree,point2);
	/*
	     (9, 4)
	    /      \
	  (2,8)    (11,12)     
	     \      /    \
	     (3,9)(14,8)  (10,13)
		                  
	-----------------
	After Remove (8, 9)
	*/
	printf("\n After Delete Tree Nodes\n");
	
	// Print  tree elements in inorder  form
	printTree(tree->root, tree->k);

	return 0;
}

Output

 Before Delete Tree Nodes
 ( 7 , 6)
 ( 2 , 8)
 ( 3 , 9)
 ( 8 , 9)
 ( 9 , 4)
 ( 14 , 8)
 ( 11 , 12)
 ( 10 , 13)

 Remove point
 ( 7 , 6)

 After Delete Tree Nodes
 ( 2 , 8)
 ( 3 , 9)
 ( 8 , 9)
 ( 9 , 4)
 ( 14 , 8)
 ( 11 , 12)
 ( 10 , 13)

 Remove point
 ( 8 , 9)

 After Delete Tree Nodes
 ( 2 , 8)
 ( 3 , 9)
 ( 9 , 4)
 ( 14 , 8)
 ( 11 , 12)
 ( 10 , 13)