Posted on by Kalkicode
Code Tree

# 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)
{
auxiliary->left = createNode(data, tree->k);
// break the loop
auxiliary = NULL;
}
else
{
// visit left subtree
auxiliary = auxiliary->left;
}
}
else
{
if (auxiliary->right == NULL)
{
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)
{
auxiliary.left = new TreeNode(data, this.k);
// break the loop
auxiliary = null;
}
else
{
// visit left subtree
auxiliary = auxiliary.left;
}
}
else
{
if (auxiliary.right == null)
{
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)
{
auxiliary->left = new TreeNode(data, this->k);
// break the loop
auxiliary = NULL;
}
else
{
// visit left subtree
auxiliary = auxiliary->left;
}
}
else
{
if (auxiliary->right == NULL)
{
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)
{
auxiliary.left = new TreeNode(data, this.k);
// break the loop
auxiliary = null;
}
else
{
// visit left subtree
auxiliary = auxiliary.left;
}
}
else
{
if (auxiliary.right == null)
{
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)
{
\$auxiliary->left = new TreeNode(\$data, \$this->k);
// break the loop
\$auxiliary = null;
}
else
{
// visit left subtree
\$auxiliary = \$auxiliary->left;
}
}
else
{
if (\$auxiliary->right == null)
{
\$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)
{
auxiliary.left = new TreeNode(data, this.k);
// break the loop
auxiliary = null;
}
else
{
// visit left subtree
auxiliary = auxiliary.left;
}
}
else
{
if (auxiliary.right == null)
{
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) :
auxiliary.left = TreeNode(data, self.k)
#  break the loop
auxiliary = None
else :
#  visit left subtree
auxiliary = auxiliary.left

else :
if (auxiliary.right == None) :
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_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_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)
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)
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)
{
auxiliary.left = new TreeNode(data, this.k);
// break the loop
auxiliary = null;
}
else
{
// visit left subtree
auxiliary = auxiliary.left;
}
}
else
{
if (auxiliary.right == null)
{
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)
{
auxiliary!.left = TreeNode(data, self.k);
// break the loop
auxiliary = nil;
}
else
{
// visit left subtree
auxiliary = auxiliary!.left;
}
}
else
{
if (auxiliary!.right == nil)
{
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)
{
auxiliary.left = TreeNode(data, this.k);
// break the loop
auxiliary = null;
}
else
{
// visit left subtree
auxiliary = auxiliary.left;
}
}
else
{
if (auxiliary.right == null)
{
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.

## 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.

Categories
Relative Post