Posted on by Kalkicode
Code Tree

# K dimensional tree insertion

The problem at hand deals with the insertion and search operations on a K-dimensional tree. A K-dimensional tree, also known as a KD-tree, is a data structure used to organize points in a K-dimensional space. It enables efficient searching of points and range queries. This problem specifically involves implementing the insertion of points into the KD-tree and searching for points within the tree.

## Problem Statement and Description

Given a set of points in a two-dimensional space, the objective is to construct a KD-tree that efficiently stores these points. The KD-tree is a binary tree where each node represents a point, and the tree is organized based on the values of the coordinates of these points. The algorithm should also be able to search for a given point in the constructed KD-tree and determine whether the point exists within the tree or not.

## Example

Let's consider a simple example to understand the problem better. We have the following 2D points:

``(8, 2), (7, 4), (3, 5), (11, 2), (5, 8), (9, 4), (2, 3)``
``````    (8,2)
/    \
(7,4)  (11,2)
/   \     \
(2,3) (3,5)  (9,4)
\
(5,8)
-----------------
Developed tree
``````

## Idea to Solve

1. Create Tree

First, we need to define the structures for the tree nodes and the KD-tree. The `createTree` function initializes an empty KD-tree.

2. Insertion

To insert a point into the KD-tree, we start at the root and traverse the tree based on the values of the coordinates. If the current node's coordinate is greater than the new point's coordinate along the current axis, we move to the left child; otherwise, we move to the right child. This continues until we find an appropriate spot to insert the new point as a leaf node.

3. Search

Searching for a point in the KD-tree is similar to insertion. We start at the root and traverse the tree based on the coordinate values. If the current node's coordinates match the search point's coordinates, we've found the point. Otherwise, we continue moving left or right based on the comparison of the coordinates.

4. Print Tree

To visualize the KD-tree, we perform an in-order traversal and print each node's coordinates.

## Pseudocode

Here's a simplified version of the pseudocode to perform insertion and search in a 2D KD-tree:

``````struct TreeNode:
int[] keys
TreeNode left
TreeNode right

struct KTree:
int k
TreeNode root

function createTree(k):
tree = new KTree
tree.k = k
tree.root = NULL
return tree

function createNode(data, k):
node = new TreeNode
node.keys = data
node.left = NULL
node.right = NULL
return node

function insert(tree, data):
if tree.root is NULL:
tree.root = createNode(data, tree.k)
else:
auxiliary = tree.root
depth = 0
axis = 0
while auxiliary is not NULL:
axis = depth % tree.k
if auxiliary.keys[axis] > data[axis]:
if auxiliary.left is NULL:
auxiliary.left = createNode(data, tree.k)
auxiliary = NULL
else:
auxiliary = auxiliary.left
else:
if auxiliary.right is NULL:
auxiliary.right = createNode(data, tree.k)
auxiliary = NULL
else:
auxiliary = auxiliary.right
depth = depth + 1

function search(tree, point):
auxiliary = tree.root
depth = 0
axis = 0
while auxiliary is not NULL:
axis = depth % tree.k
if auxiliary.keys == point:
return "Found"
else if auxiliary.keys[axis] > point[axis]:
auxiliary = auxiliary.left
else:
auxiliary = auxiliary.right
depth = depth + 1
``````// C program for
// K dimensional tree insertion
#include <stdio.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;
}
// Check if given point exists in tree or not
void search(struct KTree *tree, int point[])
{
if (tree->root != NULL)
{
struct TreeNode *auxiliary = tree->root;
int depth = 0;
int axis = 0;
int result = 0;
// Find node point
while (auxiliary != NULL && result == 0)
{
axis = depth % tree->k;
if (isEquals(auxiliary->keys, point, tree->k) == 1)
{
// When get resultant node
result = 1;
auxiliary = NULL;
}
else if (auxiliary->keys[axis] > point[axis])
{
// visit left subtree
auxiliary = auxiliary->left;
}
else
{
// visit right subtree
auxiliary = auxiliary->right;
}
depth++;
}
printf("\n Given point : ");
printData(point, tree->k);
if (result == 1)
{
printf(" Found \n");
}
else
{
}
}
else
{
printf("\n Empty Tree");
}
}
int main(int argc, char const *argv[])
{
// Number of Dimensions
int k = 2;
struct KTree *tree = createTree(k);
// 2d points
int data[][2] = {
{
8 , 2
},
{
7 , 4
},
{
3 , 5
},
{
11, 2
},
{
5 , 8
},
{
9 , 4
},
{
2 , 3
}
};

// 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 Tree Nodes\n");
/*
(8,2)
/    \
(7,4)  (11,2)
/   \     \
(2,3) (3,5)  (9,4)
\
(5,8)
-----------------
Developed tree
*/
// Print  tree elements in inorder  form
printTree(tree->root, tree->k);

// Search nodes
int point1[] = {
8 , 1
};
int point2[] = {
5 , 8
};
int point3[] = {
5 , 4
};
// Test case for find nodes
search(tree, point1);
search(tree, point2);
search(tree, point3);
return 0;
}``````

#### Output

`````` Tree Nodes
( 2 , 3)
( 7 , 4)
( 3 , 5)
( 5 , 8)
( 8 , 2)
( 11 , 2)
( 9 , 4)

Given point :  ( 8 , 1)

Given point :  ( 5 , 8)
Found

Given point :  ( 5 , 4)
``````// Java Program
// K dimensional tree insertion

// 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;
}
// Check if given point exists in tree or not
public void search(int[] point)
{
if (this.root != null)
{
TreeNode auxiliary = this.root;
int depth = 0;
int axis = 0;
boolean result = false;
// Find node point
while (auxiliary != null && result == false)
{
axis = depth % this.k;
if (isEquals(auxiliary.keys, point) == true)
{
// When get resultant node
result = true;
auxiliary = null;
}
else if (auxiliary.keys[axis] > point[axis])
{
// visit left subtree
auxiliary = auxiliary.left;
}
else
{
// visit right subtree
auxiliary = auxiliary.right;
}
depth++;
}
System.out.print("\n Given point : ");
printData(point);
if (result == true)
{
System.out.print(" Found \n");
}
else
{
}
}
else
{
System.out.print("\n Empty Tree");
}
}
public static void main(String[] args)
{
int k = 2;
KTree tree = new KTree(2);

// 2d points
int[][] data = {
{
8 , 2
} ,
{
7 , 4
} ,
{
3 , 5
} ,
{
11 , 2
} ,
{
5 , 8
} ,
{
9 , 4
} ,
{
2 , 3
}
};
// 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,2)
/    \
(7,4)  (11,2)
/   \     \
(2,3) (3,5)  (9,4)
\
(5,8)
-----------------
Developed tree
*/
// Print  tree elements in inorder  form
tree.printTree(tree.root);
// Search nodes
int[] point1 = {
8 , 1
};
int[] point2 = {
5 , 8
};
int[] point3 = {
5 , 4
};
// Test case for find nodes
tree.search(point1);
tree.search(point2);
tree.search(point3);

}
}``````

#### Output

`````` Tree Nodes
( 2 , 3)
( 7 , 4)
( 3 , 5)
( 5 , 8)
( 8 , 2)
( 11 , 2)
( 9 , 4)

Given point :  ( 8 , 1)

Given point :  ( 5 , 8)
Found

Given point :  ( 5 , 4)
``````// Include header file
#include <iostream>
using namespace std;
// C++ Program
// K dimensional tree insertion

// 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;
}
// Check if given point exists in tree or not
void search(int point[])
{
if (this->root != NULL)
{
TreeNode *auxiliary = this->root;
int depth = 0;
int axis = 0;
bool result = false;
// Find node point
while (auxiliary != NULL && result == false)
{
axis = depth % this->k;
if (this->isEquals(auxiliary->keys, point) == true)
{
// When get resultant node
result = true;
auxiliary = NULL;
}
else if (auxiliary->keys[axis] > point[axis])
{
// visit left subtree
auxiliary = auxiliary->left;
}
else
{
// visit right subtree
auxiliary = auxiliary->right;
}
depth++;
}
cout << "\n Given point : ";
this->printData(point);
if (result == true)
{
cout << " Found \n";
}
else
{
}
}
else
{
cout << "\n Empty Tree";
}
}
};
int main()
{
int k = 2;
KTree tree = KTree(2);
// 2d points
int data[][2] = {
{
8 , 2
} ,
{
7 , 4
} ,
{
3 , 5
} ,
{
11 , 2
} ,
{
5 , 8
} ,
{
9 , 4
} ,
{
2 , 3
}
};
// 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,2)
/    \
(7,4)  (11,2)
/   \     \
(2,3) (3,5)  (9,4)
\
(5,8)
-----------------
Developed tree
*/
// Print  tree elements in inorder  form
tree.printTree(tree.root);
// Search nodes
int point1[] = {
8 , 1
};
int point2[] = {
5 , 8
};
int point3[] = {
5 , 4
};
// Test case for find nodes
tree.search(point1);
tree.search(point2);
tree.search(point3);
return 0;
}``````

#### Output

`````` Tree Nodes
( 2 , 3)
( 7 , 4)
( 3 , 5)
( 5 , 8)
( 8 , 2)
( 11 , 2)
( 9 , 4)

Given point :  ( 8 , 1)

Given point :  ( 5 , 8)
Found

Given point :  ( 5 , 4)
``````<?php
// Php Program
// K dimensional tree insertion

// 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;
}
// Check if given point exists in tree or not
public	function search( \$point)
{
if (\$this->root != null)
{
\$auxiliary = \$this->root;
\$depth = 0;
\$axis = 0;
\$result = false;
// Find node point
while (\$auxiliary != null && \$result == false)
{
\$axis = \$depth % \$this->k;
if (\$this->isEquals(\$auxiliary->keys, \$point) == true)
{
// When get resultant node
\$result = true;
\$auxiliary = null;
}
else if (\$auxiliary->keys[\$axis] > \$point[\$axis])
{
// visit left subtree
\$auxiliary = \$auxiliary->left;
}
else
{
// visit right subtree
\$auxiliary = \$auxiliary->right;
}
\$depth++;
}
echo "\n Given point : ";
\$this->printData(\$point);
if (\$result == true)
{
echo " Found \n";
}
else
{
}
}
else
{
echo "\n Empty Tree";
}
}
}

function main()
{
\$k = 2;
\$tree = new KTree(\$k);
// 2d points
\$data = array(
array(8, 2),
array(7, 4),
array(3, 5),
array(11, 2),
array(5, 8),
array(9, 4),
array(2, 3)
);
// 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);
// Search nodes
\$point1 = array(8, 1);
\$point2 = array(5, 8);
\$point3 = array(5, 4);
\$tree->search(\$point1);
\$tree->search(\$point2);
\$tree->search(\$point3);
}
main();``````

#### Output

`````` Tree Nodes
( 2 , 3)
( 7 , 4)
( 3 , 5)
( 5 , 8)
( 8 , 2)
( 11 , 2)
( 9 , 4)

Given point :  ( 8 , 1)

Given point :  ( 5 , 8)
Found

Given point :  ( 5 , 4)
``````// Node Js Program
// K dimensional tree insertion

// 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;
}
// Check if given point exists in tree or not
search(point)
{
if (this.root != null)
{
var auxiliary = this.root;
var depth = 0;
var axis = 0;
var result = false;
// Find node point
while (auxiliary != null && result == false)
{
axis = depth % this.k;
if (this.isEquals(auxiliary.keys, point) == true)
{
// When get resultant node
result = true;
auxiliary = null;
}
else if (auxiliary.keys[axis] > point[axis])
{
// visit left subtree
auxiliary = auxiliary.left;
}
else
{
// visit right subtree
auxiliary = auxiliary.right;
}
depth++;
}
process.stdout.write("\n Given point : ");
this.printData(point);
if (result == true)
{
process.stdout.write(" Found \n");
}
else
{
}
}
else
{
process.stdout.write("\n Empty Tree");
}
}
}

function main()
{
var k = 2;
var tree = new KTree(k);
// 2d points
var data = [
[8, 2] , [7, 4] , [3, 5] ,
[11, 2] ,
[5, 8] , [9, 4] , [2, 3]
];
// 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,2)
/    \
(7,4)  (11,2)
/   \     \
(2,3) (3,5)  (9,4)
\
(5,8)
-----------------
Developed tree
*/
// Print  tree elements in inorder  form
tree.printTree(tree.root);
// Search nodes
var point1 = [8, 1];
var point2 = [5, 8];
var point3 = [5, 4];
// Test case for find nodes
tree.search(point1);
tree.search(point2);
tree.search(point3);
}
main();``````

#### Output

`````` Tree Nodes
( 2 , 3)
( 7 , 4)
( 3 , 5)
( 5 , 8)
( 8 , 2)
( 11 , 2)
( 9 , 4)

Given point :  ( 8 , 1)

Given point :  ( 5 , 8)
Found

Given point :  ( 5 , 4)
``````#  Python 3 Program
#  K dimensional tree insertion

#  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

#  Check if given point exists in tree or not
def search(self, point) :
if (self.root != None) :
auxiliary = self.root
depth = 0
axis = 0
result = False
#  Find node point
while (auxiliary != None and result == False) :
axis = depth % self.k
if (self.isEquals(auxiliary.keys, point) == True) :
#  When get resultant node
result = True
auxiliary = None

elif(auxiliary.keys[axis] > point[axis]) :
#  visit left subtree
auxiliary = auxiliary.left
else :
#  visit right subtree
auxiliary = auxiliary.right

depth += 1

print("\n Given point : ", end = "")
self.printData(point)
if (result == True) :
print(" Found ")
else :

else :
print("\n Empty Tree", end = "")

def main() :
k = 2
tree = KTree(k)
#  2d points
data = [
[8, 2] , [7, 4] , [3, 5] , [11, 2] ,
[5, 8] , [9, 4] , [2, 3]
]
#  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,2)
#            /    \
#          (7,4)  (11,2)
#          /   \     \
#        (2,3) (3,5)  (9,4)
#                \
#                 (5,8)
#        -----------------
#        Developed tree

#  Print  tree elements in inorder  form
tree.printTree(tree.root)
#  Search nodes
point1 = [8, 1]
point2 = [5, 8]
point3 = [5, 4]
#  Test case for find nodes
tree.search(point1)
tree.search(point2)
tree.search(point3)

if __name__ == "__main__": main()``````

#### Output

`````` Tree Nodes
(  2 ,  3)
(  7 ,  4)
(  3 ,  5)
(  5 ,  8)
(  8 ,  2)
(  11 ,  2)
(  9 ,  4)

Given point :  (  8 ,  1)

Given point :  (  5 ,  8)
Found

Given point :  (  5 ,  4)
``````#  Ruby Program
#  K dimensional tree insertion

#  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

#  Check if given point exists in tree or not
def search(point)
if (self.root != nil)
auxiliary = self.root
depth = 0
axis = 0
result = false
#  Find node point
while (auxiliary != nil && result == false)
axis = depth % self.k
if (self.isEquals(auxiliary.keys, point) == true)
#  When get resultant node
result = true
auxiliary = nil
elsif(auxiliary.keys[axis] > point[axis])
#  visit left subtree
auxiliary = auxiliary.left
else
#  visit right subtree
auxiliary = auxiliary.right
end

depth += 1
end

print("\n Given point : ")
self.printData(point)
if (result == true)
print(" Found \n")
else
end

else
print("\n Empty Tree")
end

end

end

def main()
k = 2
tree = KTree.new(k)
#  2d points
data = [
[8, 2] , [7, 4] , [3, 5] , [11, 2] , [5, 8] , [9, 4] , [2, 3]
]
#  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,2)
#            /    \
#          (7,4)  (11,2)
#          /   \     \
#        (2,3) (3,5)  (9,4)
#                \
#                 (5,8)
#        -----------------
#        Developed tree

#  Print  tree elements in inorder  form
tree.printTree(tree.root)
#  Search nodes
point1 = [8, 1]
point2 = [5, 8]
point3 = [5, 4]
#  Test case for find nodes
tree.search(point1)
tree.search(point2)
tree.search(point3)
end

main()``````

#### Output

`````` Tree Nodes
( 2 , 3)
( 7 , 4)
( 3 , 5)
( 5 , 8)
( 8 , 2)
( 11 , 2)
( 9 , 4)

Given point :  ( 8 , 1)

Given point :  ( 5 , 8)
Found

Given point :  ( 5 , 4)
``````
``````// Scala Program
// K dimensional tree insertion

// 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);

this.setValue(data,k);
}
def setValue(data: Array[Int], k : Int): Unit =
{
var i = 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;
}
// Check if given point exists in tree or not
def search(point: Array[Int]): Unit = {
if (this.root != null)
{
var auxiliary: TreeNode = this.root;
var depth: Int = 0;
var axis: Int = 0;
var result: Boolean = false;
// Find node point
while (auxiliary != null && result == false)
{
axis = depth % this.k;
if (this.isEquals(auxiliary.keys, point) == true)
{
// When get resultant node
result = true;
auxiliary = null;
}
else if (auxiliary.keys(axis) > point(axis))
{
// visit left subtree
auxiliary = auxiliary.left;
}
else
{
// visit right subtree
auxiliary = auxiliary.right;
}
depth += 1;
}
print("\n Given point : ");
this.printData(point);
if (result == true)
{
print(" Found \n");
}
else
{
}
}
else
{
print("\n Empty Tree");
}
}
}
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, 2), Array(7, 4), Array(3, 5),
Array(11, 2), Array(5, 8), Array(9, 4),
Array(2, 3)
);
// 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,2)
/    \
(7,4)  (11,2)
/   \     \
(2,3) (3,5)  (9,4)
\
(5,8)
-----------------
Developed tree
*/
// Print  tree elements in inorder  form
tree.printTree(tree.root);
// Search nodes
var point1: Array[Int] = Array(8, 1);
var point2: Array[Int] = Array(5, 8);
var point3: Array[Int] = Array(5, 4);
// Test case for find nodes
tree.search(point1);
tree.search(point2);
tree.search(point3);
}
}``````

#### Output

`````` Tree Nodes
( 2 , 3)
( 7 , 4)
( 3 , 5)
( 5 , 8)
( 8 , 2)
( 11 , 2)
( 9 , 4)

Given point :  ( 8 , 1)

Given point :  ( 5 , 8)
Found

Given point :  ( 5 , 4)
``````// Swift 4 Program
// K dimensional tree insertion

// 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;
}
// Check if given point exists in tree or not
func search(_ point: [Int])
{
if (self.root  != nil)
{
var auxiliary: TreeNode? = self.root;
var depth: Int = 0;
var axis: Int = 0;
var result: Bool = false;
// Find node point
while (auxiliary  != nil && result == false)
{
axis = depth % self.k;
if (self.isEquals(auxiliary!.keys, point) == true)
{
// When get resultant node
result = true;
auxiliary = nil;
}
else if (auxiliary!.keys[axis] > point[axis])
{
// visit left subtree
auxiliary = auxiliary!.left;
}
else
{
// visit right subtree
auxiliary = auxiliary!.right;
}
depth += 1;
}
print("\n Given point : ", terminator: "");
self.printData(point);
if (result == true)
{
print(" Found ");
}
else
{
}
}
else
{
print("\n Empty Tree", terminator: "");
}
}
}
func main()
{
let k: Int = 2;
let tree: KTree = KTree(k);
// 2d points
let data: [[Int]] =
[
[8, 2] , [7, 4] , [3, 5] ,
[11, 2] , [5, 8] , [9, 4] , [2, 3]
];
// 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,2)
/    \
(7,4)  (11,2)
/   \     \
(2,3) (3,5)  (9,4)
\
(5,8)
-----------------
Developed tree
*/
// Print  tree elements in inorder  form
tree.printTree(tree.root);
// Search nodes
let point1: [Int] = [8, 1];
let point2: [Int] = [5, 8];
let point3: [Int] = [5, 4];
// Test case for find nodes
tree.search(point1);
tree.search(point2);
tree.search(point3);
}
main();``````

#### Output

`````` Tree Nodes
(  2 ,  3)
(  7 ,  4)
(  3 ,  5)
(  5 ,  8)
(  8 ,  2)
(  11 ,  2)
(  9 ,  4)

Given point :  (  8 ,  1)

Given point :  (  5 ,  8)
Found

Given point :  (  5 ,  4)
``````// Kotlin Program
// K dimensional tree insertion

// 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;
}
// Check if given point exists in tree or not
fun search(point: Array < Int > ): Unit
{
if (this.root != null)
{
var auxiliary: TreeNode ? = this.root;
var depth: Int = 0;
var axis: Int ;
var result: Boolean = false;
// Find node point
while (auxiliary != null && result == false)
{
axis = depth % this.k;
if (this.isEquals(auxiliary.keys, point) == true)
{
// When get resultant node
result = true;
auxiliary = null;
}
else if (auxiliary.keys[axis] > point[axis])
{
// visit left subtree
auxiliary = auxiliary.left;
}
else
{
// visit right subtree
auxiliary = auxiliary.right;
}
depth += 1;
}
print("\n Given point : ");
this.printData(point);
if (result == true)
{
print(" Found \n");
}
else
{
}
}
else
{
print("\n Empty Tree");
}
}
}
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, 2), arrayOf(7, 4), arrayOf(3, 5), arrayOf(11, 2), arrayOf(5, 8), arrayOf(9, 4), arrayOf(2, 3));
// 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,2)
/    \
(7,4)  (11,2)
/   \     \
(2,3) (3,5)  (9,4)
\
(5,8)
-----------------
Developed tree
*/
// Print  tree elements in inorder  form
tree.printTree(tree.root);
// Search nodes
var point1: Array < Int > = arrayOf(8, 1);
var point2: Array < Int > = arrayOf(5, 8);
var point3: Array < Int > = arrayOf(5, 4);
// Test case for find nodes
tree.search(point1);
tree.search(point2);
tree.search(point3);
}``````

#### Output

`````` Tree Nodes
( 2 , 3)
( 7 , 4)
( 3 , 5)
( 5 , 8)
( 8 , 2)
( 11 , 2)
( 9 , 4)

Given point :  ( 8 , 1)

Given point :  ( 5 , 8)
Found

Given point :  ( 5 , 4)

## Time Complexity

• The insertion operation takes O(log n) time on average, where n is the number of nodes in the tree.
• The search operation also takes O(log n) time on average, as the tree is balanced.

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