Skip to main content

Node deletion in K dimensional tree

Node deletion in a K-dimensional tree is a fundamental operation in computational geometry and data structures. A K-dimensional tree, also known as a KD-tree, is a binary tree structure that is used to organize points in K-dimensional space for efficient search, insertion, and deletion operations. Each node in the KD-tree represents a point in K-dimensional space, and the tree is constructed in a way that allows for efficient partitioning of the space.

Problem Statement and Description

Given a K-dimensional tree and a point in K-dimensional space, the problem is to efficiently delete the node representing that point from the tree. This involves adjusting the structure of the KD-tree while maintaining its properties, such as balanced subdivision of space and efficient search capabilities.

Example

Let's consider a simple example to understand the problem. We have a 2-dimensional tree with the following points:

(8, 9), (7, 6), (3, 9), (11, 12), (2, 8), (9, 4), (10, 13), (14, 8)

Developed tree:


	     (8, 9)
	    /      \
	  (7,6)    (11,12)     
	     \      /    \
	     (3,9)(9,4)  (10,13)
		/        \
	  (2,8)      (14,8) 

We want to delete the points (7, 6) from the tree.


	     (8, 9)
	    /      \
	  (2,8)    (11,12)     
	     \      /    \
	     (3,9)(9,4)  (10,13)
		         \
	  		      (14,8)          
	-----------------
		After Remove (7,6)

Idea to Solve

To delete a node from a KD-tree, we need to find the node representing the point to be deleted, adjust the tree structure accordingly, and maintain the KD-tree properties. This involves finding a suitable replacement for the deleted node and potentially rebalancing the tree.

Pseudocode

function removeNode(node, k, point, depth):
    if node is NULL:
        return NULL
    
    dim = depth % k
    
    if point matches node's key:
        if node has a right subtree:
            min = findMinimum(node's right subtree, dim, k, depth)
            copyData(node's key, min's key, k)
            node's right subtree = removeNode(node's right subtree, k, min's key, depth + 1)
        else if node has a left subtree:
            min = findMinimum(node's left subtree, dim, k, depth)
            copyData(node's key, min's key, k)
            node's right subtree = removeNode(node's left subtree, k, min's key, depth + 1)
        else:
            free(node)
            return NULL
        return node
    
    if point's key in current dimension is smaller than node's key:
        node's left subtree = removeNode(node's left subtree, k, point, depth + 1)
    else:
        node's right subtree = removeNode(node's right subtree, k, point, depth + 1)
    
    return node

function deleteNode(tree, point):
    tree's root = removeNode(tree's root, tree's k, point, 0)

Algorithm Explanation

The pseudocode outlines the process of deleting a node from the KD-tree. It handles three cases: when the node to be deleted has a right subtree, when it has a left subtree, and when it is a leaf node.

Code Solution

// 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)
// Java Program 
// Node deletion in K dimensional tree  


// Define tree node
class TreeNode
{
    public int []keys;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int[] data,int k)
    {
        this.keys = new int[k];
        this.left = null;
        this.right = null;

        for (int i = 0; i < k; ++i)
        {
            this.keys[i] = data[i];
        }
   }
}
public class KTree
{
    public int k;

    public TreeNode root;

    public KTree(int k)
    {
        this.k = k;
        this.root = null;
    }

    // Handles the request to add new node in Tree
    public void insert(int[] data)
    {
        if (this.root == null)
        {
            // When add first node of tree
            this.root = new TreeNode(data, this.k);
        }
        else
        {
            TreeNode auxiliary = this.root;
            int depth = 0;
            int axis = 0;
            // Add new node in tree
            while (auxiliary != null)
            {
                axis = depth % this.k;
                if (auxiliary.keys[axis] > data[axis])
                {
                    if (auxiliary.left == null)
                    {
                        // Add new node
                        auxiliary.left = new TreeNode(data, this.k);
                        // break the loop
                        auxiliary = null;
                    }
                    else
                    {
                        // visit left subtree
                        auxiliary = auxiliary.left;
                    }
                }
                else
                {
                    if (auxiliary.right == null)
                    {
                        // Add new node
                        auxiliary.right = new TreeNode(data, this.k);
                        // break the loop
                        auxiliary = null;
                    }
                    else
                    {
                        // visit right subtree
                        auxiliary = auxiliary.right;
                    }
                }
                depth++;
            }
        }
    }
    //  Print the all key of a given node
    public void printData(int[] data)
    {
        System.out.print(" (");
        for (int i = 0; i < this.k; ++i)
        {
            if (i > 0)
            {
                System.out.print(" , " + data[i] );
            }
            else
            {
                System.out.print(" " + data[i] );
            }
        }
        System.out.print(")\n");
    }
    // Display tree node
    public void printTree(TreeNode node)
    {
        if (node != null)
        {
            printTree(node.left);
            printData(node.keys);
            printTree(node.right);
        }
    }
    // Compare node and given point
    public boolean isEquals(int[] node, int[] point)
    {
        for (int i = 0; i < this.k; ++i)
        {
            if (node[i] != point[i])
            {
                return false;
            }
        }
        //  When both are same
        return true;
    }
    // return the minimum node by using of given dimension
    public TreeNode minPoint(TreeNode node1, 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
    public TreeNode findMinimum(TreeNode node, int dim, 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, 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, depth + 1), 
          findMinimum(node.right, dim, depth + 1), dim), dim);
    }
    // Handles the request of find minimum point using given dimensions
    public void minimum(int dim)
    {
        if (this.root == null)
        {
            System.out.print("\n Empty Tree");
        }
        else if (dim < 0 || dim + 1 > this.k)
        {
            System.out.print("\n Given dimensions are not valid ");
        }
        else
        {
            TreeNode n = findMinimum(this.root, dim, 0);
            System.out.print("\n Given Dimension : " + dim );
            if (n != null)
            {
                System.out.print("\n Minimum is : " + n.keys[dim] );
            }
        }
    }
    // Copy node 2 value into node1
    public void copyData(int[] node1, int[] node2)
    {
        for (int i = 0; i < this.k; i++)
        {
            node1[i] = node2[i];
        }
    }
    // Handles the request of remove given point node in tree
    public TreeNode removeNode(TreeNode node, int[] point, int depth)
    {
        if (node == null)
        {
          	System.out.println("Point not exist");
            return null;
        }
        int dim = depth % this.k;
        if (isEquals(node.keys, point))
        {
            // 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
                TreeNode min = findMinimum(node.right, dim, 0);
                // minimum point replace by current node
                copyData(node.keys, min.keys);
                // Recursively find new minimum deleted point
                node.right = removeNode(node.right, 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
                TreeNode min = findMinimum(node.left, dim, 0);
                // minimum point replace by current node
                copyData(node.keys, min.keys);
                // Recursively find new minimum deleted point
                node.right = removeNode(node.left, min.keys, depth + 1);
            }
            else
            {
                // Case 3 :  When current node is leaf node
                // Then remove it
                node = null;
                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, point, depth + 1);
        }
        else
        {
            node.right = removeNode(node.right, point, depth + 1);
        }
        return node;
    }
    // Handles the request to delete given point in tree
    public void deleteNode( int[] point)
    {
        if (this.root == null)
        {
            System.out.print("\n Empty Tree");
            return;
        }
        System.out.print("\n Remove point \n");
        printData(point);
        // Assuming that the given point length is equal to the tree node keys
        this.root = removeNode(this.root, point, 0);
    }
    public static void main(String[] args)
    {   
        int k = 2;
        KTree tree = new KTree(k);

        // 2d points
        int[][] data = {
            {
                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 = data.length;
        // Insert all given nodes
        for (int i = 0; i < n; ++i)
        {
            tree.insert(data[i]);
        }
        System.out.print("\n 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
        tree.printTree(tree.root);
        // Case 1
        tree.deleteNode( point1);
        /*
             (8, 9)
            /      \
          (2,8)    (11,12)     
             \      /    \
             (3,9)(9,4)  (10,13)
                     \
                      (14,8)          
        -----------------
            After Remove (7,6)
        */
        System.out.print("\n After Delete Tree Nodes\n");
        // Print  tree elements in inorder  form
        tree.printTree(tree.root);
        // Case 2
        tree.deleteNode(point2);
        /*
             (9, 4)
            /      \
          (2,8)    (11,12)     
             \      /    \
             (3,9)(14,8)  (10,13)
                              
        -----------------
        After Remove (8, 9)
        */
        System.out.print("\n After Delete Tree Nodes\n");
        // Print  tree elements in inorder  form
        tree.printTree(tree.root);
    }
}

Output

 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)
// Include header file
#include <iostream>
using namespace std;
// C++ Program
// Node deletion in K dimensional tree

// Define tree node
class TreeNode
{
	public: 
    int *keys;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int data[], int k)
	{
		this->keys = new int[k];
		this->left = NULL;
		this->right = NULL;
		for (int i = 0; i < k; ++i)
		{
			this->keys[i] = data[i];
		}
	}
};
class KTree
{
	public: int k;
	TreeNode *root;
	KTree(int k)
	{
		this->k = k;
		this->root = NULL;
	}
	// Handles the request to add new node in Tree
	void insert(int data[])
	{
		if (this->root == NULL)
		{
			// When add first node of tree
			this->root = new TreeNode(data, this->k);
		}
		else
		{
			TreeNode *auxiliary = this->root;
			int depth = 0;
			int axis = 0;
			// Add new node in tree
			while (auxiliary != NULL)
			{
				axis = depth % this->k;
				if (auxiliary->keys[axis] > data[axis])
				{
					if (auxiliary->left == NULL)
					{
						// Add new node
						auxiliary->left = new TreeNode(data, this->k);
						// break the loop
						auxiliary = NULL;
					}
					else
					{
						// visit left subtree
						auxiliary = auxiliary->left;
					}
				}
				else
				{
					if (auxiliary->right == NULL)
					{
						// Add new node
						auxiliary->right = new TreeNode(data, this->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[])
	{
		cout << " (";
		for (int i = 0; i < this->k; ++i)
		{
			if (i > 0)
			{
				cout << " , " << data[i];
			}
			else
			{
				cout << " " << data[i];
			}
		}
		cout << ")\n";
	}
	// Display tree node
	void printTree(TreeNode *node)
	{
		if (node != NULL)
		{
			this->printTree(node->left);
			this->printData(node->keys);
			this->printTree(node->right);
		}
	}
	// Compare node and given point
	bool isEquals(int node[], int point[])
	{
		//  When both are same
		for (int i = 0; i < this->k; ++i)
		{
			if (node[i] != point[i])
			{
				return false;
			}
		}
		return true;
	}
	// return the minimum node by using of given dimension
	TreeNode *minPoint(TreeNode *node1, TreeNode *node2, int dim)
	{
		// Node 2 is smaller
		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;
		}
		return node2;
	}
	// Recursively finding the minimum of given dimension
	TreeNode *findMinimum(TreeNode *node, int dim, int depth)
	{
		if (node == NULL)
		{
			// When get a null Node
			return NULL;
		}
		// Get dimension position
		int position = depth % this->k;
		if (position == dim)
		{
			// When position are equal to given a dimension
			if (node->left == NULL)
			{
				// Returns the current dimension
				return node;
			}
			return this->minPoint(node, 
                   this->findMinimum(node->left, dim, depth + 1), dim);
		}
		// When position are equal to given a dimension
		// Then resultant node can be exists in left or right subtree
		return this->minPoint(node, 
               this->minPoint(this->findMinimum(node->left, dim, depth + 1), 
               this->findMinimum(node->right, dim, depth + 1), dim), dim);
	}
	// Handles the request of find minimum point using given dimensions
	void minimum(int dim)
	{
		if (this->root == NULL)
		{
			cout << "\n Empty Tree";
		}
		else if (dim < 0 || dim + 1 > this->k)
		{
			cout << "\n Given dimensions are not valid ";
		}
		else
		{
			TreeNode *n = this->findMinimum(this->root, dim, 0);
			cout << "\n Given Dimension : " << dim;
			if (n != NULL)
			{
				cout << "\n Minimum is : " << n->keys[dim];
			}
		}
	}
	// Copy node 2 value into node1
	void copyData(int node1[], int node2[])
	{
		for (int i = 0; i < this->k; i++)
		{
			node1[i] = node2[i];
		}
	}
	// Handles the request of remove given point node in tree
	TreeNode *removeNode(TreeNode *node, int point[], int depth)
	{
		if (node == NULL)
		{
			cout << "Point not exist";
			return NULL;
		}
		int dim = depth % this->k;
		if (this->isEquals(node->keys, point))
		{
			// 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
				TreeNode *min = this->findMinimum(node->right, dim, 0);
				// minimum point replace by current node
				this->copyData(node->keys, min->keys);
				// Recursively find new minimum deleted point
				node->right = this->removeNode(node->right, 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
				TreeNode *min = this->findMinimum(node->left, dim, 0);
				// minimum point replace by current node
				this->copyData(node->keys, min->keys);
				// Recursively find new minimum deleted point
				node->right = this->removeNode(node->left, min->keys, depth + 1);
			}
			else
			{
				// Case 3 :  When current node is leaf node
				// Then remove it
              	delete node;
				node = NULL;
			}
			return node;
		}
		// Choose the left and right subtree by using given point
		if (node->keys[dim] > point[dim])
		{
			node->left = this->removeNode(node->left, point, depth + 1);
		}
		else
		{
			node->right = this->removeNode(node->right, point, depth + 1);
		}
		return node;
	}
	// Handles the request to delete given point in tree
	void deleteNode(int point[])
	{
		if (this->root == NULL)
		{
			cout << "\n Empty Tree";
			return;
		}
		cout << "\n Remove point \n";
		this->printData(point);
		// Assuming that the given point length is equal to the tree node keys
		this->root = this->removeNode(this->root, point, 0);
	}
};
int main()
{
	int k = 2;
	KTree tree = KTree(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)
	{
		tree.insert(data[i]);
	}
	cout << "\n 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
	tree.printTree(tree.root);
	// Case 1
	tree.deleteNode(point1);
	/*
	             (8, 9)
	            /      \
	          (2,8)    (11,12)     
	             \      /    \
	             (3,9)(9,4)  (10,13)
	                     \
	                      (14,8)          
	        -----------------
	            After Remove (7,6)
	        */
	cout << "\n After Delete Tree Nodes\n";
	// Print  tree elements in inorder  form
	tree.printTree(tree.root);
	// Case 2
	tree.deleteNode(point2);
	/*
	             (9, 4)
	            /      \
	          (2,8)    (11,12)     
	             \      /    \
	             (3,9)(14,8)  (10,13)
	                              
	        -----------------
	        After Remove (8, 9)
	        */
	cout << "\n After Delete Tree Nodes\n";
	// Print  tree elements in inorder  form
	tree.printTree(tree.root);
	return 0;
}

Output

 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)
// Include namespace system
using System;
using System.Collections;
using System.Linq;
// C# Program
// Node deletion in K dimensional tree

// Define tree node
public class TreeNode
{
	public int[] keys;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int[] data, int k)
	{
		this.keys = new int[k];
		this.left = null;
		this.right = null;
		for (int i = 0; i < k; ++i)
		{
			this.keys[i] = data[i];
		}
	}
}
public class KTree
{
	public int k;
	public TreeNode root;
	public KTree(int k)
	{
		this.k = k;
		this.root = null;
	}
	// Handles the request to add new node in Tree
	public void insert(int[] data)
	{
		if (this.root == null)
		{
			// When add first node of tree
			this.root = new TreeNode(data, this.k);
		}
		else
		{
			TreeNode auxiliary = this.root;
			int depth = 0;
			int axis = 0;
			// Add new node in tree
			while (auxiliary != null)
			{
				axis = depth % this.k;
				if (auxiliary.keys[axis] > data[axis])
				{
					if (auxiliary.left == null)
					{
						// Add new node
						auxiliary.left = new TreeNode(data, this.k);
						// break the loop
						auxiliary = null;
					}
					else
					{
						// visit left subtree
						auxiliary = auxiliary.left;
					}
				}
				else
				{
					if (auxiliary.right == null)
					{
						// Add new node
						auxiliary.right = new TreeNode(data, this.k);
						// break the loop
						auxiliary = null;
					}
					else
					{
						// visit right subtree
						auxiliary = auxiliary.right;
					}
				}
				depth++;
			}
		}
	}
	//  Print the all key of a given node
	public void printData(int[] data)
	{
		Console.Write(" (");
		for (int i = 0; i < this.k; ++i)
		{
			if (i > 0)
			{
				Console.Write(" , " + data[i]);
			}
			else
			{
				Console.Write(" " + data[i]);
			}
		}
		Console.Write(")\n");
	}
	// Display tree node
	public void printTree(TreeNode node)
	{
		if (node != null)
		{
			printTree(node.left);
			printData(node.keys);
			printTree(node.right);
		}
	}
	// Compare node and given point
	public Boolean isEquals(int[] node, int[] point)
	{
		//  When both are same
		for (int i = 0; i < this.k; ++i)
		{
			if (node[i] != point[i])
			{
				return false;
			}
		}
		return true;
	}
	// return the minimum node by using of given dimension
	public TreeNode minPoint(TreeNode node1, TreeNode node2, int dim)
	{
		// Node 2 is smaller
		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;
		}
		return node2;
	}
	// Recursively finding the minimum of given dimension
	public TreeNode findMinimum(TreeNode node, int dim, 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, 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, depth + 1), findMinimum(node.right, dim, depth + 1), dim), dim);
	}
	// Handles the request of find minimum point using given dimensions
	public void minimum(int dim)
	{
		if (this.root == null)
		{
			Console.Write("\n Empty Tree");
		}
		else if (dim < 0 || dim + 1 > this.k)
		{
			Console.Write("\n Given dimensions are not valid ");
		}
		else
		{
			TreeNode n = findMinimum(this.root, dim, 0);
			Console.Write("\n Given Dimension : " + dim);
			if (n != null)
			{
				Console.Write("\n Minimum is : " + n.keys[dim]);
			}
		}
	}
	// Copy node 2 value into node1
	public void copyData(int[] node1, int[] node2)
	{
		for (int i = 0; i < this.k; i++)
		{
			node1[i] = node2[i];
		}
	}
	// Handles the request of remove given point node in tree
	public TreeNode removeNode(TreeNode node, int[] point, int depth)
	{
		if (node == null)
		{
			Console.WriteLine("Point not exist");
			return null;
		}
		int dim = depth % this.k;
		if (isEquals(node.keys, point))
		{
			// 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
				TreeNode min = findMinimum(node.right, dim, 0);
				// minimum point replace by current node
				copyData(node.keys, min.keys);
				// Recursively find new minimum deleted point
				node.right = removeNode(node.right, 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
				TreeNode min = findMinimum(node.left, dim, 0);
				// minimum point replace by current node
				copyData(node.keys, min.keys);
				// Recursively find new minimum deleted point
				node.right = removeNode(node.left, min.keys, depth + 1);
			}
			else
			{
				// Case 3 :  When current node is leaf node
				// Then remove it
				node = null;
			}
			return node;
		}
		// Choose the left and right subtree by using given point
		if (node.keys[dim] > point[dim])
		{
			node.left = removeNode(node.left, point, depth + 1);
		}
		else
		{
			node.right = removeNode(node.right, point, depth + 1);
		}
		return node;
	}
	// Handles the request to delete given point in tree
	public void deleteNode(int[] point)
	{
		if (this.root == null)
		{
			Console.Write("\n Empty Tree");
			return;
		}
		Console.Write("\n Remove point \n");
		printData(point);
		// Assuming that the given point length is equal to the tree node keys
		this.root = removeNode(this.root, point, 0);
	}
	public static void Main(String[] args)
	{
		int k = 2;
		KTree tree = new KTree(k);
		// 2d points
		int[,] data = {
			{
				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 = data.GetLength(0);
		// Insert all given nodes
		for (int i = 0; i < n; ++i)
		{
			tree.insert(Enumerable.Range(0, data.GetLength(1))
                .Select(x => data[i, x])
                .ToArray());
		}
		Console.Write("\n 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
		tree.printTree(tree.root);
		// Case 1
		tree.deleteNode(point1);
		/*
             (8, 9)
            /      \
          (2,8)    (11,12)     
             \      /    \
             (3,9)(9,4)  (10,13)
                     \
                      (14,8)          
        -----------------
            After Remove (7,6)
        */
		Console.Write("\n After Delete Tree Nodes\n");
		// Print  tree elements in inorder  form
		tree.printTree(tree.root);
		// Case 2
		tree.deleteNode(point2);
		/*
             (9, 4)
            /      \
          (2,8)    (11,12)     
             \      /    \
             (3,9)(14,8)  (10,13)
                              
        -----------------
        After Remove (8, 9)
        */
		Console.Write("\n After Delete Tree Nodes\n");
		// Print  tree elements in inorder  form
		tree.printTree(tree.root);
	}
}

Output

 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)
<?php
// Php Program
// Node deletion in K dimensional tree

// Define tree node
class TreeNode
{
	public $keys;
	public $left;
	public $right;

	function __construct( & $data, $k)
	{
		$this->keys = array_fill(0, $k, 0);
		$this->left = null;
		$this->right = null;
		for ($i = 0; $i < $k; ++$i)
		{
			$this->keys[$i] = $data[$i];
		}
	}
}
class KTree
{
	public $k;
	public $root;

	function __construct($k)
	{
		$this->k = $k;
		$this->root = null;
	}
	// Handles the request to add new node in Tree
	public	function insert( & $data)
	{
		if ($this->root == null)
		{
			// When add first node of tree
			$this->root = new TreeNode($data, $this->k);
		}
		else
		{
			$auxiliary = $this->root;
			$depth = 0;
			$axis = 0;
			// Add new node in tree
			while ($auxiliary != null)
			{
				$axis = $depth % $this->k;
				if ($auxiliary->keys[$axis] > $data[$axis])
				{
					if ($auxiliary->left == null)
					{
						// Add new node
						$auxiliary->left = new TreeNode($data, $this->k);
						// break the loop
						$auxiliary = null;
					}
					else
					{
						// visit left subtree
						$auxiliary = $auxiliary->left;
					}
				}
				else
				{
					if ($auxiliary->right == null)
					{
						// Add new node
						$auxiliary->right = new TreeNode($data, $this->k);
						// break the loop
						$auxiliary = null;
					}
					else
					{
						// visit right subtree
						$auxiliary = $auxiliary->right;
					}
				}
				$depth++;
			}
		}
	}
	//  Print the all key of a given node
	public	function printData( & $data)
	{
		echo " (";
		for ($i = 0; $i < $this->k; ++$i)
		{
			if ($i > 0)
			{
				echo " , ". $data[$i];
			}
			else
			{
				echo " ". $data[$i];
			}
		}
		echo ")\n";
	}
	// Display tree node
	public	function printTree($node)
	{
		if ($node != null)
		{
			$this->printTree($node->left);
			$this->printData($node->keys);
			$this->printTree($node->right);
		}
	}
	// Compare node and given point
	public	function isEquals( & $node, & $point)
	{
		//  When both are same
		for ($i = 0; $i < $this->k; ++$i)
		{
			if ($node[$i] != $point[$i])
			{
				return false;
			}
		}
		return true;
	}
	// return the minimum node by using of given dimension
	public	function minPoint($node1, $node2, $dim)
	{
		// Node 2 is smaller
		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;
		}
		return $node2;
	}
	// Recursively finding the minimum of given dimension
	public	function findMinimum($node, $dim, $depth)
	{
		if ($node == null)
		{
			// When get a null Node
			return null;
		}
		// Get dimension position
		$position = $depth % $this->k;
		if ($position == $dim)
		{
			// When position are equal to given a dimension
			if ($node->left == null)
			{
				// Returns the current dimension
				return $node;
			}
			return $this->minPoint($node, $this->findMinimum($node->left, $dim, $depth + 1), $dim);
		}
		// When position are equal to given a dimension
		// Then resultant node can be exists in left or right subtree
		return $this->minPoint($node, $this->minPoint($this->findMinimum($node->left, $dim, $depth + 1), $this->findMinimum($node->right, $dim, $depth + 1), $dim), $dim);
	}
	// Handles the request of find minimum point using given dimensions
	public	function minimum($dim)
	{
		if ($this->root == null)
		{
			echo "\n Empty Tree";
		}
		else if ($dim < 0 || $dim + 1 > $this->k)
		{
			echo "\n Given dimensions are not valid ";
		}
		else
		{
			$n = $this->findMinimum($this->root, $dim, 0);
			echo "\n Given Dimension : ". $dim;
			if ($n != null)
			{
				echo "\n Minimum is : ". $n->keys[$dim];
			}
		}
	}
	// Copy node 2 value into node1
	public	function copyData( & $node1, & $node2)
	{
		for ($i = 0; $i < $this->k; $i++)
		{
			$node1[$i] = $node2[$i];
		}
	}
	// Handles the request of remove given point node in tree
	public	function removeNode($node, & $point, $depth)
	{
		if ($node == null)
		{
			echo "Point not exist";
			return null;
		}
		$dim = $depth % $this->k;
		if ($this->isEquals($node->keys, $point))
		{
			// 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
				$min = $this->findMinimum($node->right, $dim, 0);
				// minimum point replace by current node
				$this->copyData($node->keys, $min->keys);
				// Recursively find new minimum deleted point
				$node->right = $this->removeNode($node->right, $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
				$min = $this->findMinimum($node->left, $dim, 0);
				// minimum point replace by current node
				$this->copyData($node->keys, $min->keys);
				// Recursively find new minimum deleted point
				$node->right = $this->removeNode($node->left, $min->keys, $depth + 1);
			}
			else
			{
				// Case 3 :  When current node is leaf node
				// Then remove it
				$node = null;
			}
			return $node;
		}
		// Choose the left and right subtree by using given point
		if ($node->keys[$dim] > $point[$dim])
		{
			$node->left = $this->removeNode($node->left, $point, $depth + 1);
		}
		else
		{
			$node->right = $this->removeNode($node->right, $point, $depth + 1);
		}
		return $node;
	}
	// Handles the request to delete given point in tree
	public	function deleteNode( & $point)
	{
		if ($this->root == null)
		{
			echo "\n Empty Tree";
			return;
		}
		echo "\n Remove point \n";
		$this->printData($point);
		// Assuming that the given point length is equal to the tree node keys
		$this->root = $this->removeNode($this->root, $point, 0);
	}
}

function main()
{
	$k = 2;
	$tree = new KTree($k);
	// 2d points
	$data = array(array(8, 9), array(7, 6), array(3, 9), array(11, 12), array(2, 8), array(9, 4), array(10, 13), array(14, 8));
	// Remove node points
	$point1 = array(7, 6);
	$point2 = array(8, 9);
	// Get the number of elements
	$n = count($data);
	// Insert all given nodes
	for ($i = 0; $i < $n; ++$i)
	{
		$tree->insert($data[$i]);
	}
	echo "\n Tree Nodes\n";
	$tree->printTree($tree->root);
	$tree->deleteNode($point1);
	/*
	             (8, 9)
	            /      \
	          (2,8)    (11,12)     
	             \      /    \
	             (3,9)(9,4)  (10,13)
	                     \
	                      (14,8)          
	        -----------------
	            After Remove (7,6)
	        
	*/
	echo "\n After Delete Tree Nodes\n";
	$tree->printTree($tree->root);
	$tree->deleteNode($point2);
	/*
	             (9, 4)
	            /      \
	          (2,8)    (11,12)     
	             \      /    \
	             (3,9)(14,8)  (10,13)
	                              
	        -----------------
	        After Remove (8, 9)
	        
	*/
	echo "\n After Delete Tree Nodes\n";
	$tree->printTree($tree->root);
}
main();

Output

 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)
// Node Js Program
// Node deletion in K dimensional tree

// Define tree node
class TreeNode
{
	constructor(data, k)
	{
		this.keys = Array(k).fill(0);
		this.left = null;
		this.right = null;
		for (var i = 0; i < k; ++i)
		{
			this.keys[i] = data[i];
		}
	}
}
class KTree
{
	constructor(k)
	{
		this.k = k;
		this.root = null;
	}
	// Handles the request to add new node in Tree
	insert(data)
	{
		if (this.root == null)
		{
			// When add first node of tree
			this.root = new TreeNode(data, this.k);
		}
		else
		{
			var auxiliary = this.root;
			var depth = 0;
			var axis = 0;
			// Add new node in tree
			while (auxiliary != null)
			{
				axis = depth % this.k;
				if (auxiliary.keys[axis] > data[axis])
				{
					if (auxiliary.left == null)
					{
						// Add new node
						auxiliary.left = new TreeNode(data, this.k);
						// break the loop
						auxiliary = null;
					}
					else
					{
						// visit left subtree
						auxiliary = auxiliary.left;
					}
				}
				else
				{
					if (auxiliary.right == null)
					{
						// Add new node
						auxiliary.right = new TreeNode(data, this.k);
						// break the loop
						auxiliary = null;
					}
					else
					{
						// visit right subtree
						auxiliary = auxiliary.right;
					}
				}
				depth++;
			}
		}
	}
	//  Print the all key of a given node
	printData(data)
	{
		process.stdout.write(" (");
		for (var i = 0; i < this.k; ++i)
		{
			if (i > 0)
			{
				process.stdout.write(" , " + data[i]);
			}
			else
			{
				process.stdout.write(" " + data[i]);
			}
		}
		process.stdout.write(")\n");
	}
	// Display tree node
	printTree(node)
	{
		if (node != null)
		{
			this.printTree(node.left);
			this.printData(node.keys);
			this.printTree(node.right);
		}
	}
	// Compare node and given point
	isEquals(node, point)
	{
		//  When both are same
		for (var i = 0; i < this.k; ++i)
		{
			if (node[i] != point[i])
			{
				return false;
			}
		}
		return true;
	}
	// return the minimum node by using of given dimension
	minPoint(node1, node2, dim)
	{
		// Node 2 is smaller
		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;
		}
		return node2;
	}
	// Recursively finding the minimum of given dimension
	findMinimum(node, dim, depth)
	{
		if (node == null)
		{
			// When get a null Node
			return null;
		}
		// Get dimension position
		var position = depth % this.k;
		if (position == dim)
		{
			// When position are equal to given a dimension
			if (node.left == null)
			{
				// Returns the current dimension
				return node;
			}
			return this.minPoint(node, this.findMinimum(node.left, dim, depth + 1), dim);
		}
		// When position are equal to given a dimension
		// Then resultant node can be exists in left or right subtree
		return this.minPoint(node, this.minPoint(this.findMinimum(node.left, dim, depth + 1), this.findMinimum(node.right, dim, depth + 1), dim), dim);
	}
	// Handles the request of find minimum point using given dimensions
	minimum(dim)
	{
		if (this.root == null)
		{
			process.stdout.write("\n Empty Tree");
		}
		else if (dim < 0 || dim + 1 > this.k)
		{
			process.stdout.write("\n Given dimensions are not valid ");
		}
		else
		{
			var n = this.findMinimum(this.root, dim, 0);
			process.stdout.write("\n Given Dimension : " + dim);
			if (n != null)
			{
				process.stdout.write("\n Minimum is : " + n.keys[dim]);
			}
		}
	}
	// Copy node 2 value into node1
	copyData(node1, node2)
	{
		for (var i = 0; i < this.k; i++)
		{
			node1[i] = node2[i];
		}
	}
	// Handles the request of remove given point node in tree
	removeNode(node, point, depth)
	{
		if (node == null)
		{
			process.stdout.write("Point not exist");
			return null;
		}
		var dim = depth % this.k;
		if (this.isEquals(node.keys, point))
		{
			// 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
				var min = this.findMinimum(node.right, dim, 0);
				// minimum point replace by current node
				this.copyData(node.keys, min.keys);
				// Recursively find new minimum deleted point
				node.right = this.removeNode(node.right, 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
				var min = this.findMinimum(node.left, dim, 0);
				// minimum point replace by current node
				this.copyData(node.keys, min.keys);
				// Recursively find new minimum deleted point
				node.right = this.removeNode(node.left, min.keys, depth + 1);
			}
			else
			{
				// Case 3 :  When current node is leaf node
				// Then remove it
				node = null;
			}
			return node;
		}
		// Choose the left and right subtree by using given point
		if (node.keys[dim] > point[dim])
		{
			node.left = this.removeNode(node.left, point, depth + 1);
		}
		else
		{
			node.right = this.removeNode(node.right, point, depth + 1);
		}
		return node;
	}
	// Handles the request to delete given point in tree
	deleteNode(point)
	{
		if (this.root == null)
		{
			process.stdout.write("\n Empty Tree");
			return;
		}
		process.stdout.write("\n Remove point \n");
		this.printData(point);
		// Assuming that the given point length is equal to the tree node keys
		this.root = this.removeNode(this.root, point, 0);
	}
}

function main()
{
	var k = 2;
	var tree = new KTree(k);
	// 2d points
	var data = [
		[8, 9] , [7, 6] , [3, 9] , [11, 12] , [2, 8] , [9, 4] , [10, 13] , [14, 8]
	];
	// Remove node points
	var point1 = [7, 6];
	var point2 = [8, 9];
	// Get the number of elements
	var n = data.length;
	// Insert all given nodes
	for (var i = 0; i < n; ++i)
	{
		tree.insert(data[i]);
	}
	process.stdout.write("\n 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
	tree.printTree(tree.root);
	// Case 1
	tree.deleteNode(point1);
	/*
	             (8, 9)
	            /      \
	          (2,8)    (11,12)     
	             \      /    \
	             (3,9)(9,4)  (10,13)
	                     \
	                      (14,8)          
	        -----------------
	            After Remove (7,6)
	        */
	process.stdout.write("\n After Delete Tree Nodes\n");
	// Print  tree elements in inorder  form
	tree.printTree(tree.root);
	// Case 2
	tree.deleteNode(point2);
	/*
	             (9, 4)
	            /      \
	          (2,8)    (11,12)     
	             \      /    \
	             (3,9)(14,8)  (10,13)
	                              
	        -----------------
	        After Remove (8, 9)
	        */
	process.stdout.write("\n After Delete Tree Nodes\n");
	// Print  tree elements in inorder  form
	tree.printTree(tree.root);
}
main();

Output

 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)
#  Python 3 Program
#  Node deletion in K dimensional tree

#  Define tree node
class TreeNode :
	
	def __init__(self, data, k) :
		self.keys = [0] * (k)
		self.left = None
		self.right = None
		i = 0
		while (i < k) :
			self.keys[i] = data[i]
			i += 1
		

class KTree :
	
	def __init__(self, k) :
		self.k = k
		self.root = None
	
	#  Handles the request to add new node in Tree
	def insert(self, data) :
		if (self.root == None) :
			#  When add first node of tree
			self.root = TreeNode(data, self.k)
		else :
			auxiliary = self.root
			depth = 0
			axis = 0
			#  Add new node in tree
			while (auxiliary != None) :
				axis = depth % self.k
				if (auxiliary.keys[axis] > data[axis]) :
					if (auxiliary.left == None) :
						#  Add new node
						auxiliary.left = TreeNode(data, self.k)
						#  break the loop
						auxiliary = None
					else :
						#  visit left subtree
						auxiliary = auxiliary.left
					
				else :
					if (auxiliary.right == None) :
						#  Add new node
						auxiliary.right = TreeNode(data, self.k)
						#  break the loop
						auxiliary = None
					else :
						#  visit right subtree
						auxiliary = auxiliary.right
					
				
				depth += 1
			
		
	
	#   Print the all key of a given node
	def printData(self, data) :
		print(" (", end = "")
		i = 0
		while (i < self.k) :
			if (i > 0) :
				print(" , ", data[i], end = "")
			else :
				print(" ", data[i], end = "")
			
			i += 1
		
		print(")")
	
	#  Display tree node
	def printTree(self, node) :
		if (node != None) :
			self.printTree(node.left)
			self.printData(node.keys)
			self.printTree(node.right)
		
	
	#  Compare node and given point
	def isEquals(self, node, point) :
		#   When both are same
		i = 0
		while (i < self.k) :
			if (node[i] != point[i]) :
				return False
			
			i += 1
		
		return True
	
	#  return the minimum node by using of given dimension
	def minPoint(self, node1, node2, dim) :
		#  Node 2 is smaller
		if (node1 == None) :
			#  When node 1 empty
			return node2
		
		if (node2 == None) :
			#  When node 2 empty
			return node1
		
		if (node1.keys[dim] < node2.keys[dim]) :
			#  Node 1 is smaller
			return node1
		
		return node2
	
	#  Recursively finding the minimum of given dimension
	def findMinimum(self, node, dim, depth) :
		if (node == None) :
			#  When get a null Node
			return None
		
		#  Get dimension position
		position = depth % self.k
		if (position == dim) :
			#  When position are equal to given a dimension
			if (node.left == None) :
				#  Returns the current dimension
				return node
			
			return self.minPoint(node, 
                   self.findMinimum(node.left, dim, depth + 1), dim)
		
		#  When position are equal to given a dimension
		#  Then resultant node can be exists in left or right subtree
		return self.minPoint(node, 
               self.minPoint(self.findMinimum(node.left, dim, depth + 1),
              self.findMinimum(node.right, dim, depth + 1), dim), dim)
	
	#  Handles the request of find minimum point using given dimensions
	def minimum(self, dim) :
		if (self.root == None) :
			print("\n Empty Tree", end = "")
		
		elif(dim < 0 or dim + 1 > self.k) :
			print("\n Given dimensions are not valid ", end = "")
		else :
			n = self.findMinimum(self.root, dim, 0)
			print("\n Given Dimension : ", dim, end = "")
			if (n != None) :
				print("\n Minimum is : ", n.keys[dim], end = "")
			
		
	
	#  Copy node 2 value into node1
	def copyData(self, node1, node2) :
		i = 0
		while (i < self.k) :
			node1[i] = node2[i]
			i += 1
		
	
	#  Handles the request of remove given point node in tree
	def removeNode(self, node, point, depth) :
		if (node == None) :
			print("Point not exist", end = "")
			return None
		
		dim = depth % self.k
		if (self.isEquals(node.keys, point)) :
			#  When current node is same as deleted point
			#  Here are three possibility
			if (node.right != None) :
				#  Case 1 : When right subtree not NULL
				#  Then find minimum node point and replace by current node
				min = self.findMinimum(node.right, dim, 0)
				#  minimum point replace by current node
				self.copyData(node.keys, min.keys)
				#  Recursively find new minimum deleted point
				node.right = self.removeNode(node.right, min.keys, depth + 1)
			
			elif(node.left != None) :
				#  Case 2 : When current node left subtree not Empty
				#  Then find minimum node point in left subtree and
				#  replace by current node
				min = self.findMinimum(node.left, dim, 0)
				#  minimum point replace by current node
				self.copyData(node.keys, min.keys)
				#  Recursively find new minimum deleted point
				node.right = self.removeNode(node.left, min.keys, depth + 1)
			else :
				#  Case 3 :  When current node is leaf node
				#  Then remove it
				node = None
			
			return node
		
		#  Choose the left and right subtree by using given point
		if (node.keys[dim] > point[dim]) :
			node.left = self.removeNode(node.left, point, depth + 1)
		else :
			node.right = self.removeNode(node.right, point, depth + 1)
		
		return node
	
	#  Handles the request to delete given point in tree
	def deleteNode(self, point) :
		if (self.root == None) :
			print("\n Empty Tree", end = "")
			return
		
		print("\n Remove point ")
		self.printData(point)
		#  Assuming that the given point length is equal to the tree node keys
		self.root = self.removeNode(self.root, point, 0)
	

def main() :
	k = 2
	tree = KTree(k)
	#  2d points
	data = [
		[8, 9] , [7, 6] , [3, 9] , [11, 12] , 
        [2, 8] , [9, 4] , [10, 13] , [14, 8]
	]
	#  Remove node points
	point1 = [7, 6]
	point2 = [8, 9]
	#  Get the number of elements
	n = len(data)
	#  Insert all given nodes
	i = 0
	while (i < n) :
		tree.insert(data[i])
		i += 1
	
	print("\n Tree Nodes")
	# 
	# 		            (8, 9)
	# 		           /      \
	# 		         (7,6)    (11,12)     
	# 		            \      /    \
	# 		            (3,9)(9,4)  (10,13)
	# 		           /        \
	# 		         (2,8)      (14,8)         
	# 		       -----------------
	# 		       Developed tree
	# 		       
	
	#  Print  tree elements in inorder  form
	tree.printTree(tree.root)
	#  Case 1
	tree.deleteNode(point1)
	# 
	# 		            (8, 9)
	# 		           /      \
	# 		         (2,8)    (11,12)     
	# 		            \      /    \
	# 		            (3,9)(9,4)  (10,13)
	# 		                    \
	# 		                     (14,8)          
	# 		       -----------------
	# 		           After Remove (7,6)
	# 		       
	
	print("\n After Delete Tree Nodes")
	#  Print  tree elements in inorder  form
	tree.printTree(tree.root)
	#  Case 2
	tree.deleteNode(point2)
	# 
	# 		            (9, 4)
	# 		           /      \
	# 		         (2,8)    (11,12)     
	# 		            \      /    \
	# 		            (3,9)(14,8)  (10,13)
	# 		                             
	# 		       -----------------
	# 		       After Remove (8, 9)
	# 		       
	
	print("\n After Delete Tree Nodes")
	#  Print  tree elements in inorder  form
	tree.printTree(tree.root)

if __name__ == "__main__": main()

Output

 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)
#  Ruby Program
#  Node deletion in K dimensional tree

#  Define tree node
class TreeNode  
	# Define the accessor and reader of class TreeNode  
	attr_reader :keys, :left, :right
	attr_accessor :keys, :left, :right
 
	
	def initialize(data, k) 
		self.keys = Array.new(k) {0}
		self.left = nil
		self.right = nil
		i = 0
		while (i < k) 
			self.keys[i] = data[i]
			i += 1
		end

	end

end

class KTree  
	# Define the accessor and reader of class KTree  
	attr_reader :k, :root
	attr_accessor :k, :root
 
	
	def initialize(k) 
		self.k = k
		self.root = nil
	end

	#  Handles the request to add new node in Tree
	def insert(data) 
		if (self.root == nil) 
			#  When add first node of tree
			self.root = TreeNode.new(data, self.k)
		else 
			auxiliary = self.root
			depth = 0
			axis = 0
			#  Add new node in tree
			while (auxiliary != nil) 
				axis = depth % self.k
				if (auxiliary.keys[axis] > data[axis]) 
					if (auxiliary.left == nil) 
						#  Add new node
						auxiliary.left = TreeNode.new(data, self.k)
						#  break the loop
						auxiliary = nil
					else 
						#  visit left subtree
						auxiliary = auxiliary.left
					end

				else 
					if (auxiliary.right == nil) 
						#  Add new node
						auxiliary.right = TreeNode.new(data, self.k)
						#  break the loop
						auxiliary = nil
					else 
						#  visit right subtree
						auxiliary = auxiliary.right
					end

				end

				depth += 1
			end

		end

	end

	#   Print the all key of a given node
	def printData(data) 
		print(" (")
		i = 0
		while (i < self.k) 
			if (i > 0) 
				print(" , ", data[i])
			else 
				print(" ", data[i])
			end

			i += 1
		end

		print(")\n")
	end

	#  Display tree node
	def printTree(node) 
		if (node != nil) 
			self.printTree(node.left)
			self.printData(node.keys)
			self.printTree(node.right)
		end

	end

	#  Compare node and given point
	def isEquals(node, point) 
		#   When both are same
		i = 0
		while (i < self.k) 
			if (node[i] != point[i]) 
				return false
			end

			i += 1
		end

		return true
	end

	#  return the minimum node by using of given dimension
	def minPoint(node1, node2, dim) 
		#  Node 2 is smaller
		if (node1 == nil) 
			#  When node 1 empty
			return node2
		end

		if (node2 == nil) 
			#  When node 2 empty
			return node1
		end

		if (node1.keys[dim] < node2.keys[dim]) 
			#  Node 1 is smaller
			return node1
		end

		return node2
	end

	#  Recursively finding the minimum of given dimension
	def findMinimum(node, dim, depth) 
		if (node == nil) 
			#  When get a null Node
			return nil
		end

		#  Get dimension position
		position = depth % k
		if (position == dim) 
			#  When position are equal to given a dimension
			if (node.left == nil) 
				#  Returns the current dimension
				return node
			end

			return self.minPoint(node, 
                       self.findMinimum(node.left, dim, depth + 1), dim)
		end

		#  When position are equal to given a dimension
		#  Then resultant node can be exists in left or right subtree
		return self.minPoint(node, 
                   self.minPoint(self.findMinimum(node.left, dim, depth + 1), 
                        self.findMinimum(node.right, dim, depth + 1), dim), dim)
	end

	#  Handles the request of find minimum point using given dimensions
	def minimum(dim) 
		if (self.root == nil) 
			print("\n Empty Tree")
		elsif(dim < 0 || dim + 1 > self.k) 
			print("\n Given dimensions are not valid ")
		else 
			n = self.findMinimum(self.root, dim, 0)
			print("\n Given Dimension : ", dim)
			if (n != nil) 
				print("\n Minimum is : ", n.keys[dim])
			end

		end

	end

	#  Copy node 2 value into node1
	def copyData(node1, node2) 
		i = 0
		while (i < self.k) 
			node1[i] = node2[i]
			i += 1
		end

	end

	#  Handles the request of remove given point node in tree
	def removeNode(node, point, depth) 
		if (node == nil) 
			print("Point not exist")
			return nil
		end

		dim = depth % self.k
		if (self.isEquals(node.keys, point)) 
			#  When current node is same as deleted point
			#  Here are three possibility
			if (node.right != nil) 
				#  Case 1 : When right subtree not NULL
				#  Then find minimum node point and replace by current node
				min = self.findMinimum(node.right, dim, 0)
				#  minimum point replace by current node
				self.copyData(node.keys, min.keys)
				#  Recursively find new minimum deleted point
				node.right = self.removeNode(node.right, min.keys, depth + 1)
			elsif(node.left != nil) 
				#  Case 2 : When current node left subtree not Empty
				#  Then find minimum node point in left subtree and
				#  replace by current node
				min = self.findMinimum(node.left, dim, 0)
				#  minimum point replace by current node
				self.copyData(node.keys, min.keys)
				#  Recursively find new minimum deleted point
				node.right = self.removeNode(node.left, min.keys, depth + 1)
			else 
				#  Case 3 :  When current node is leaf node
				#  Then remove it
				node = nil
			end

			return node
		end

		#  Choose the left and right subtree by using given point
		if (node.keys[dim] > point[dim]) 
			node.left = self.removeNode(node.left, point, depth + 1)
		else 
			node.right = self.removeNode(node.right, point, depth + 1)
		end

		return node
	end

	#  Handles the request to delete given point in tree
	def deleteNode(point) 
		if (self.root == nil) 
			print("\n Empty Tree")
			return
		end

		print("\n Remove point \n")
		self.printData(point)
		#  Assuming that the given point length is equal to the tree node keys
		self.root = self.removeNode(self.root, point, 0)
	end

end

def main() 
	k = 2
	tree = KTree.new(k)
	#  2d points
	data = [
		[8, 9] , [7, 6] , [3, 9] , [11, 12] , 
      	[2, 8] , [9, 4] , [10, 13] , [14, 8]
	]
	#  Remove node points
	point1 = [7, 6]
	point2 = [8, 9]
	#  Get the number of elements
	n = data.length
	#  Insert all given nodes
	i = 0
	while (i < n) 
		tree.insert(data[i])
		i += 1
	end

	print("\n 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
	tree.printTree(tree.root)
	#  Case 1
	tree.deleteNode(point1)
	# 
	#     (8, 9)
	#    /      \
	#  (2,8)    (11,12)     
	#     \      /    \
	#     (3,9)(9,4)  (10,13)
	#             \
	#              (14,8)          
	# -----------------
	#    After Remove (7,6)
	
	print("\n After Delete Tree Nodes\n")
	#  Print  tree elements in inorder  form
	tree.printTree(tree.root)
	#  Case 2
	tree.deleteNode(point2)
	# 
	#     (9, 4)
	#    /      \
	#  (2,8)    (11,12)     
	#     \      /    \
	#     (3,9)(14,8)  (10,13)
	#                      
	# -----------------
	# After Remove (8, 9)
	
	print("\n After Delete Tree Nodes\n")
	#  Print  tree elements in inorder  form
	tree.printTree(tree.root)
end

main()

Output

 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)
// Scala Program
// Node deletion in K dimensional tree

// Define tree node
class TreeNode(var keys: Array[Int] , 
  var left: TreeNode , 
    var right: TreeNode)
{
	def this(data: Array[Int], k: Int)
	{
      	this(Array.fill[Int](k)(0), null, null);
      	var i: Int = 0
		while (i < k)
		{   
          	this.keys(i) = data(i);
			i += 1
		}
	}
}
class KTree(var k: Int , 
            var root: TreeNode)
{
	def this(k: Int)
	{
		this(k, null);
	}
	// Handles the request to add new node in Tree
	def insert(data: Array[Int]): Unit = {
		if (this.root == null)
		{
			// When add first node of tree
			this.root = new TreeNode(data, this.k);
		}
		else
		{
			var auxiliary: TreeNode = this.root;
			var depth: Int = 0;
			var axis: Int = 0;
			// Add new node in tree
			while (auxiliary != null)
			{
				axis = depth % this.k;
				if (auxiliary.keys(axis) > data(axis))
				{
					if (auxiliary.left == null)
					{
						// Add new node
						auxiliary.left = new TreeNode(data, this.k);
						// break the loop
						auxiliary = null;
					}
					else
					{
						// visit left subtree
						auxiliary = auxiliary.left;
					}
				}
				else
				{
					if (auxiliary.right == null)
					{
						// Add new node
						auxiliary.right = new TreeNode(data, this.k);
						// break the loop
						auxiliary = null;
					}
					else
					{
						// visit right subtree
						auxiliary = auxiliary.right;
					}
				}
				depth += 1;
			}
		}
	}
	//  Print the all key of a given node
	def printData(data: Array[Int]): Unit = {
		print(" (");
		var i: Int = 0;
		while (i < this.k)
		{
			if (i > 0)
			{
				print(" , " + data(i));
			}
			else
			{
				print(" " + data(i));
			}
			i += 1;
		}
		print(")\n");
	}
	// Display tree node
	def printTree(node: TreeNode): Unit = {
		if (node != null)
		{
			this.printTree(node.left);
			this.printData(node.keys);
			this.printTree(node.right);
		}
	}
	// Compare node and given point
	def isEquals(node: Array[Int], point: Array[Int]): Boolean = {
		//  When both are same
		var i: Int = 0;
		while (i < this.k)
		{
			if (node(i) != point(i))
			{
				return false;
			}
			i += 1;
		}
		return true;
	}
	// return the minimum node by using of given dimension
	def minPoint(node1: TreeNode, node2: TreeNode, dim: Int): TreeNode = {
		// Node 2 is smaller
		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;
		}
		return node2;
	}
	// Recursively finding the minimum of given dimension
	def findMinimum(node: TreeNode, dim: Int, depth: Int): TreeNode = {
		if (node == null)
		{
			// When get a null Node
			return null;
		}
		// Get dimension position
		var position: Int = depth % k;
		if (position == dim)
		{
			// When position are equal to given a dimension
			if (node.left == null)
			{
				// Returns the current dimension
				return node;
			}
			return this.minPoint(node, this.findMinimum(node.left, dim, depth + 1), dim);
		}
		// When position are equal to given a dimension
		// Then resultant node can be exists in left or right subtree
		return this.minPoint(node, this.minPoint(this.findMinimum(node.left, dim, depth + 1), this.findMinimum(node.right, dim, depth + 1), dim), dim);
	}
	// Handles the request of find minimum point using given dimensions
	def minimum(dim: Int): Unit = {
		if (this.root == null)
		{
			print("\n Empty Tree");
		}
		else if (dim < 0 || dim + 1 > this.k)
		{
			print("\n Given dimensions are not valid ");
		}
		else
		{
			var n: TreeNode = this.findMinimum(this.root, dim, 0);
			print("\n Given Dimension : " + dim);
			if (n != null)
			{
				print("\n Minimum is : " + n.keys(dim));
			}
		}
	}
	// Copy node 2 value into node1
	def copyData(node1: Array[Int], node2: Array[Int]): Unit = {
		var i: Int = 0;
		while (i < this.k)
		{
			node1(i) = node2(i);
			i += 1;
		}
	}
	// Handles the request of remove given point node in tree
	def removeNode(node: TreeNode, point: Array[Int], depth: Int): TreeNode = {
		if (node == null)
		{
			print("Point not exist");
			return null;
		}
		var dim: Int = depth % this.k;
		if (this.isEquals(node.keys, point))
		{
			// 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
				var min: TreeNode = this.findMinimum(node.right, dim, 0);
				// minimum point replace by current node
				this.copyData(node.keys, min.keys);
				// Recursively find new minimum deleted point
				node.right = this.removeNode(node.right, 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
				var min = this.findMinimum(node.left, dim, 0);
				// minimum point replace by current node
				this.copyData(node.keys, min.keys);
				// Recursively find new minimum deleted point
				node.right = this.removeNode(node.left, min.keys, depth + 1);
			}
			else
			{
				// Case 3 :  When current node is leaf node
				// Then remove it
				return null;
			}
			return node;
		}
		// Choose the left and right subtree by using given point
		if (node.keys(dim) > point(dim))
		{
			node.left = this.removeNode(node.left, point, depth + 1);
		}
		else
		{
			node.right = this.removeNode(node.right, point, depth + 1);
		}
		return node;
	}
	// Handles the request to delete given point in tree
	def deleteNode(point: Array[Int]): Unit = {
		if (this.root == null)
		{
			print("\n Empty Tree");
			return;
		}
		print("\n Remove point \n");
		this.printData(point);
		// Assuming that the given point length is equal to the tree node keys
		this.root = this.removeNode(this.root, point, 0);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var k: Int = 2;
		var tree: KTree = new KTree(k);
		// 2d points
		var data: Array[Array[Int]] = Array(
          Array(8, 9), Array(7, 6), Array(3, 9), 
          Array(11, 12), Array(2, 8), Array(9, 4), 
          Array(10, 13), Array(14, 8));
		// Remove node points
		var point1: Array[Int] = Array(7, 6);
		var point2: Array[Int] = Array(8, 9);
		// Get the number of elements
		var n: Int = data.length;
		// Insert all given nodes
		var i: Int = 0;
		while (i < n)
		{
			tree.insert(data(i));
			i += 1;
		}
		print("\n 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
		tree.printTree(tree.root);
		// Case 1
		tree.deleteNode(point1);
		/*
		    (8, 9)
		   /      \
		 (2,8)    (11,12)     
		    \      /    \
		    (3,9)(9,4)  (10,13)
		            \
		             (14,8)          
		-----------------
		   After Remove (7,6)
		*/
		print("\n After Delete Tree Nodes\n");
		// Print  tree elements in inorder  form
		tree.printTree(tree.root);
		// Case 2
		tree.deleteNode(point2);
		/*
		    (9, 4)
		   /      \
		 (2,8)    (11,12)     
		    \      /    \
		    (3,9)(14,8)  (10,13)
		                     
		-----------------
		After Remove (8, 9)
		*/
		print("\n After Delete Tree Nodes\n");
		// Print  tree elements in inorder  form
		tree.printTree(tree.root);
	}
}

Output

 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)
// Swift 4 Program
// Node deletion in K dimensional tree

// Define tree node
class TreeNode
{
	var keys: [Int];
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ data: [Int], _ k: Int)
	{
		self.keys = Array(repeating: 0, count: k);
		self.left = nil;
		self.right = nil;
		var i: Int = 0;
		while (i < k)
		{
			self.keys[i] = data[i];
			i += 1;
		}
	}
}
class KTree
{
	var k: Int;
	var root: TreeNode? ;
	init(_ k: Int)
	{
		self.k = k;
		self.root = nil;
	}
	// Handles the request to add new node in Tree
	func insert(_ data: [Int])
	{
		if (self.root == nil)
		{
			// When add first node of tree
			self.root = TreeNode(data, self.k);
		}
		else
		{
			var auxiliary: TreeNode? = self.root;
			var depth: Int = 0;
			var axis: Int = 0;
			// Add new node in tree
			while (auxiliary  != nil)
			{
				axis = depth % self.k;
				if (auxiliary!.keys[axis] > data[axis])
				{
					if (auxiliary!.left == nil)
					{
						// Add new node
						auxiliary!.left = TreeNode(data, self.k);
						// break the loop
						auxiliary = nil;
					}
					else
					{
						// visit left subtree
						auxiliary = auxiliary!.left;
					}
				}
				else
				{
					if (auxiliary!.right == nil)
					{
						// Add new node
						auxiliary!.right = TreeNode(data, self.k);
						// break the loop
						auxiliary = nil;
					}
					else
					{
						// visit right subtree
						auxiliary = auxiliary!.right;
					}
				}
				depth += 1;
			}
		}
	}
	//  Print the all key of a given node
	func printData(_ data: [Int])
	{
		print(" (", terminator: "");
		var i: Int = 0;
		while (i < self.k)
		{
			if (i > 0)
			{
				print(" , ", data[i], terminator: "");
			}
			else
			{
				print(" ", data[i], terminator: "");
			}
			i += 1;
		}
		print(")");
	}
	// Display tree node
	func printTree(_ node: TreeNode? )
	{
		if (node  != nil)
		{
			self.printTree(node!.left);
			self.printData(node!.keys);
			self.printTree(node!.right);
		}
	}
	// Compare node and given point
	func isEquals(_ node: [Int], _ point: [Int])->Bool
	{
		//  When both are same
		var i: Int = 0;
		while (i < self.k)
		{
			if (node[i]  != point[i])
			{
				return false;
			}
			i += 1;
		}
		return true;
	}
	// return the minimum node by using of given dimension
	func minPoint(_ node1: TreeNode? , _ node2 : TreeNode? , _ dim : Int)->TreeNode?
	{
		// Node 2 is smaller
		if (node1 == nil)
		{
			// When node 1 empty
			return node2;
		}
		if (node2 == nil)
		{
			// When node 2 empty
			return node1;
		}
		if (node1!.keys[dim] < node2!.keys[dim])
		{
			// Node 1 is smaller
			return node1;
		}
		return node2;
	}
	// Recursively finding the minimum of given dimension
	func findMinimum(_ node: TreeNode? , _ dim : Int, _ depth: Int)->TreeNode?
	{
		if (node == nil)
		{
			// When get a null Node
			return nil;
		}
		// Get dimension position
		let position: Int = depth % self.k;
		if (position == dim)
		{
			// When position are equal to given a dimension
			if (node!.left == nil)
			{
				// Returns the current dimension
				return node;
			}
			return self.minPoint(node, 
                        self.findMinimum(node!.left, dim, depth + 1), dim);
		}
		// When position are equal to given a dimension
		// Then resultant node can be exists in left or right subtree
		return self.minPoint(node, 
                    self.minPoint(self.findMinimum(node!.left, dim, depth + 1),
                       self.findMinimum(node!.right, dim, depth + 1), dim), dim);
	}
	// Handles the request of find minimum point using given dimensions
	func minimum(_ dim: Int)
	{
		if (self.root == nil)
		{
			print("\n Empty Tree", terminator: "");
		}
		else if (dim < 0 || dim + 1 > self.k)
		{
			print("\n Given dimensions are not valid ", terminator: "");
		}
		else
		{
			let n: TreeNode? = self.findMinimum(self.root, dim, 0);
			print("\n Given Dimension : ", dim, terminator: "");
			if (n  != nil)
			{
				print("\n Minimum is : ", n!.keys[dim], terminator: "");
			}
		}
	}
	// Copy node 2 value into node1
	func copyData(_ node1: inout[Int], _ node2: [Int])
	{
		var i: Int = 0;
		while (i < self.k)
		{
			node1[i] = node2[i];
			i += 1;
		}
	}
	// Handles the request of remove given point node in tree
	func removeNode(_ node: TreeNode? , _ point : [Int], _ depth: Int)->TreeNode?
	{
		if (node == nil)
		{
			print("Point not exist", terminator: "");
			return nil;
		}
		let dim: Int = depth % self.k;
		if (self.isEquals(node!.keys, point))
		{
			// When current node is same as deleted point
			// Here are three possibility
			if (node!.right  != nil)
			{
				// Case 1 : When right subtree not NULL
				// Then find minimum node point and replace by current node
				let min: TreeNode? = self.findMinimum(node!.right, dim, 0);
				// minimum point replace by current node
				self.copyData(&node!.keys, min!.keys);
				// Recursively find new minimum deleted point
				node!.right = self.removeNode(node!.right, min!.keys, depth + 1);
			}
			else if (node!.left  != nil)
			{
				// Case 2 : When current node left subtree not Empty
				// Then find minimum node point in left subtree and
				// replace by current node
				let min = self.findMinimum(node!.left, dim, 0);
				// minimum point replace by current node
				self.copyData(&node!.keys, min!.keys);
				// Recursively find new minimum deleted point
				node!.right = self.removeNode(node!.left, min!.keys, depth + 1);
			}
			else
			{
				// Case 3 :  When current node is leaf node
				// Then remove it
				return nil;
			}
			return node;
		}
		// Choose the left and right subtree by using given point
		if (node!.keys[dim] > point[dim])
		{
			node!.left = self.removeNode(node!.left, point, depth + 1);
		}
		else
		{
			node!.right = self.removeNode(node!.right, point, depth + 1);
		}
		return node;
	}
	// Handles the request to delete given point in tree
	func deleteNode(_ point: [Int])
	{
		if (self.root == nil)
		{
			print("\n Empty Tree", terminator: "");
			return;
		}
		print("\n Remove point ");
		self.printData(point);
		// Assuming that the given point length is equal to the tree node keys
		self.root = self.removeNode(self.root, point, 0);
	}
}
func main()
{
	let k: Int = 2;
	let tree: KTree = KTree(k);
	// 2d points
	let data: [
		[Int]
	] = [
		[8, 9] , [7, 6] , [3, 9] , [11, 12] , [2, 8] , [9, 4] , [10, 13] , [14, 8]
	];
	// Remove node points
	let point1: [Int] = [7, 6];
	let point2: [Int] = [8, 9];
	// Get the number of elements
	let n: Int = data.count;
	// Insert all given nodes
	var i: Int = 0;
	while (i < n)
	{
		tree.insert(data[i]);
		i += 1;
	}
	print("\n Tree Nodes");
	/*
	    (8, 9)
	   /      \
	 (7,6)    (11,12)     
	    \      /    \
	    (3,9)(9,4)  (10,13)
	   /        \
	 (2,8)      (14,8)         
	-----------------
	Developed tree
	*/
	// Print  tree elements in inorder  form
	tree.printTree(tree.root);
	// Case 1
	tree.deleteNode(point1);
	/*
	    (8, 9)
	   /      \
	 (2,8)    (11,12)     
	    \      /    \
	    (3,9)(9,4)  (10,13)
	            \
	             (14,8)          
	-----------------
	   After Remove (7,6)
	*/
	print("\n After Delete Tree Nodes");
	// Print  tree elements in inorder  form
	tree.printTree(tree.root);
	// Case 2
	tree.deleteNode(point2);
	/*
	    (9, 4)
	   /      \
	 (2,8)    (11,12)     
	    \      /    \
	    (3,9)(14,8)  (10,13)
	                     
	-----------------
	After Remove (8, 9)
	*/
	print("\n After Delete Tree Nodes");
	// Print  tree elements in inorder  form
	tree.printTree(tree.root);
}
main();

Output

 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)
// Kotlin Program
// Node deletion in K dimensional tree

// Define tree node
class TreeNode
{
	var keys: Array < Int > ;
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(data: Array < Int > , k: Int)
	{
		this.keys = Array(k)
		{
			0
		};
		this.left = null;
		this.right = null;
		var i: Int = 0;
		while (i < k)
		{
			this.keys[i] = data[i];
			i += 1;
		}
	}
}
class KTree
{
	var k: Int;
	var root: TreeNode ? ;
	constructor(k: Int)
	{
		this.k = k;
		this.root = null;
	}
	// Handles the request to add new node in Tree
	fun insert(data: Array < Int > ): Unit
	{
		if (this.root == null)
		{
			// When add first node of tree
			this.root = TreeNode(data, this.k);
		}
		else
		{
			var auxiliary: TreeNode ? = this.root;
			var depth: Int = 0;
			var axis: Int;
			// Add new node in tree
			while (auxiliary != null)
			{
				axis = depth % this.k;
				if (auxiliary.keys[axis] > data[axis])
				{
					if (auxiliary.left == null)
					{
						// Add new node
						auxiliary.left = TreeNode(data, this.k);
						// break the loop
						auxiliary = null;
					}
					else
					{
						// visit left subtree
						auxiliary = auxiliary.left;
					}
				}
				else
				{
					if (auxiliary.right == null)
					{
						// Add new node
						auxiliary.right = TreeNode(data, this.k);
						// break the loop
						auxiliary = null;
					}
					else
					{
						// visit right subtree
						auxiliary = auxiliary.right;
					}
				}
				depth += 1;
			}
		}
	}
	//  Print the all key of a given node
	fun printData(data: Array < Int > ): Unit
	{
		print(" (");
		var i: Int = 0;
		while (i < this.k)
		{
			if (i > 0)
			{
				print(" , " + data[i]);
			}
			else
			{
				print(" " + data[i]);
			}
			i += 1;
		}
		print(")\n");
	}
	// Display tree node
	fun printTree(node: TreeNode ? ): Unit
	{
		if (node != null)
		{
			this.printTree(node.left);
			this.printData(node.keys);
			this.printTree(node.right);
		}
	}
	// Compare node and given point
	fun isEquals(node: Array < Int > , point: Array < Int > ): Boolean
	{
		//  When both are same
		var i: Int = 0;
		while (i < this.k)
		{
			if (node[i] != point[i])
			{
				return false;
			}
			i += 1;
		}
		return true;
	}
	// return the minimum node by using of given dimension
	fun minPoint(node1: TreeNode ? , node2 : TreeNode ? , dim : Int): TreeNode ?
	{
		// Node 2 is smaller
		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;
		}
		return node2;
	}
	// Recursively finding the minimum of given dimension
	fun findMinimum(node: TreeNode ? , dim : Int, depth: Int): TreeNode ?
	{
		if (node == null)
		{
			// When get a null Node
			return null;
		}
		// Get dimension position
		var position: Int = depth % k;
		if (position == dim)
		{
			// When position are equal to given a dimension
			if (node.left == null)
			{
				// Returns the current dimension
				return node;
			}
			return this.minPoint(node, 
                        this.findMinimum(node.left, dim, depth + 1), dim);
		}
		
		// When position are equal to given a dimension
		// Then resultant node can be exists in left or right subtree
		return this.minPoint(node, 
                this.minPoint(
        			this.findMinimum(node.left, dim, depth + 1), 
          				this.findMinimum(node.right, dim, depth + 1), dim), dim);
	}
	// Handles the request of find minimum point using given dimensions
	fun minimum(dim: Int): Unit
	{
		if (this.root == null)
		{
			print("\n Empty Tree");
		}
		else if (dim < 0 || dim + 1 > this.k)
		{
			print("\n Given dimensions are not valid ");
		}
		else
		{
			var n: TreeNode? = this.findMinimum(this.root, dim, 0);
			print("\n Given Dimension : " + dim);
			if (n != null)
			{
				print("\n Minimum is : " + n.keys[dim]);
			}
		}
	}
	// Copy node 2 value into node1
	fun copyData(node1: Array < Int > , node2: Array < Int > ): Unit
	{
		var i: Int = 0;
		while (i < this.k)
		{
			node1[i] = node2[i];
			i += 1;
		}
	}
	// Handles the request of remove given point node in tree
	fun removeNode(node: TreeNode ? , point : Array <Int> , depth: Int): TreeNode ?
	{
		if (node == null)
		{
			print("Point not exist");
			return null;
		}
		var dim: Int = depth % this.k;
		if (this.isEquals(node.keys, point))
		{
			// 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
				var min: TreeNode? = this.findMinimum(node.right, dim, 0);
				// minimum point replace by current node
				this.copyData(node.keys, min!!.keys);
				// Recursively find new minimum deleted point
				node.right = this.removeNode(node.right, 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
				var min: TreeNode? = this.findMinimum(node.left, dim, 0);
				// minimum point replace by current node
				this.copyData(node.keys, min!!.keys);
				// Recursively find new minimum deleted point
				node.right = this.removeNode(node.left, min.keys, depth + 1);
			}
			else
			{
				// Case 3 :  When current node is leaf node
				// Then remove it
				return null;
			}
			return node;
		}
		// Choose the left and right subtree by using given point
		if (node.keys[dim] > point[dim])
		{
			node.left = this.removeNode(node.left, point, depth + 1);
		}
		else
		{
			node.right = this.removeNode(node.right, point, depth + 1);
		}
		return node;
	}
	// Handles the request to delete given point in tree
	fun deleteNode(point: Array < Int > ): Unit
	{
		if (this.root == null)
		{
			print("\n Empty Tree");
			return;
		}
		print("\n Remove point \n");
		this.printData(point);
		// Assuming that the given point length is equal to the tree node keys
		this.root = this.removeNode(this.root, point, 0);
	}
}
fun main(args: Array < String > ): Unit
{
	var k: Int = 2;
	var tree: KTree = KTree(k);
	// 2d points
	var data: Array < Array < Int >> = arrayOf(
      arrayOf(8, 9), 
      arrayOf(7, 6), 
      arrayOf(3, 9), 
      arrayOf(11, 12), 
      arrayOf(2, 8), 
      arrayOf(9, 4), 
      arrayOf(10, 13), 
      arrayOf(14, 8));
	// Remove node points
	var point1: Array < Int > = arrayOf(7, 6);
	var point2: Array < Int > = arrayOf(8, 9);
	// Get the number of elements
	var n: Int = data.count();
	// Insert all given nodes
	var i: Int = 0;
	while (i < n)
	{
		tree.insert(data[i]);
		i += 1;
	}
	print("\n 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
	tree.printTree(tree.root);
	// Case 1
	tree.deleteNode(point1);
	/*
	    (8, 9)
	   /      \
	 (2,8)    (11,12)     
	    \      /    \
	    (3,9)(9,4)  (10,13)
	            \
	             (14,8)          
	-----------------
	   After Remove (7,6)
	*/
	print("\n After Delete Tree Nodes\n");
	// Print  tree elements in inorder  form
	tree.printTree(tree.root);
	// Case 2
	tree.deleteNode(point2);
	/*
	    (9, 4)
	   /      \
	 (2,8)    (11,12)     
	    \      /    \
	    (3,9)(14,8)  (10,13)
	                     
	-----------------
	After Remove (8, 9)
	*/
	print("\n After Delete Tree Nodes\n");
	// Print  tree elements in inorder  form
	tree.printTree(tree.root);
}

Output

 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)

Time Complexity

The time complexity of the node deletion operation in a KD-tree depends on the height of the tree and the efficiency of the findMinimum function. In a balanced KD-tree, the height is logarithmic in the number of nodes, resulting in an average case time complexity of O(log N), where N is the number of nodes in the tree. However, in the worst case, the tree might become unbalanced, leading to a time complexity of O(N), but this is rare in practice for balanced KD-trees.

Java Code Work

Example node deletion in K dimensional tree




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment