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
    return "Not Found"
// 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)
                {
                    // Add new node
                    auxiliary->left = createNode(data, tree->k);
                    // break the loop
                    auxiliary = NULL;
                }
                else
                {
                    // visit left subtree
                    auxiliary = auxiliary->left;
                }
            }
            else
            {
                if (auxiliary->right == NULL)
                {
                    // Add new node
                    auxiliary->right = createNode(data, tree->k);
                    // break the loop
                    auxiliary = NULL;
                }
                else
                {
                    // visit right subtree
                    auxiliary = auxiliary->right;
                }
            }
            depth++;
        }
    }
}
//  Print the all key of a given node
void printData(int data[], int k)
{
    printf(" (");
    for (int i = 0; i < k; ++i)
    {
        if (i > 0)
        {
            printf(" , %d", data[i]);
        }
        else
        {
            printf(" %d", data[i]);
        }
    }
    printf(")\n");
}
// Display tree node
void printTree(struct TreeNode *node, int k)
{
    if (node != NULL)
    {
        printTree(node->left, k);
        printData(node->keys, k);
        printTree(node->right, k);
    }
}
// Compare node and given point
int isEquals(int node[], int point[], int k)
{
    for (int i = 0; i < k; ++i)
    {
        if (node[i] != point[i])
        {
            return 0;
        }
    }
    //  When both are same
    return 1;
}
// 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
        {
            printf(" Not Found \n");
        }
    }
    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)
 Not Found

 Given point :  ( 5 , 8)
 Found

 Given point :  ( 5 , 4)
 Not Found
// 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)
                    {
                        // Add new node
                        auxiliary.left = new TreeNode(data, this.k);
                        // break the loop
                        auxiliary = null;
                    }
                    else
                    {
                        // visit left subtree
                        auxiliary = auxiliary.left;
                    }
                }
                else
                {
                    if (auxiliary.right == null)
                    {
                        // Add new node
                        auxiliary.right = new TreeNode(data, this.k);
                        // break the loop
                        auxiliary = null;
                    }
                    else
                    {
                        // visit right subtree
                        auxiliary = auxiliary.right;
                    }
                }
                depth++;
            }
        }
    }
    //  Print the all key of a given node
    public void printData(int[] data)
    {
        System.out.print(" (");
        for (int i = 0; i < this.k; ++i)
        {
            if (i > 0)
            {
                System.out.print(" , " + data[i] );
            }
            else
            {
                System.out.print(" " + data[i] );
            }
        }
        System.out.print(")\n");
    }
    // Display tree node
    public void printTree(TreeNode node)
    {
        if (node != null)
        {
            printTree(node.left);
            printData(node.keys);
            printTree(node.right);
        }
    }
    // Compare node and given point
    public boolean isEquals(int[] node, int[] point)
    {
        for (int i = 0; i < this.k; ++i)
        {
            if (node[i] != point[i])
            {
                return false;
            }
        }
        //  When both are same
        return true;
    }
    // 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
            {
                System.out.print(" Not Found \n");
            }
        }
        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)
 Not Found

 Given point :  ( 5 , 8)
 Found

 Given point :  ( 5 , 4)
 Not Found
// 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)
					{
						// Add new node
						auxiliary->left = new TreeNode(data, this->k);
						// break the loop
						auxiliary = NULL;
					}
					else
					{
						// visit left subtree
						auxiliary = auxiliary->left;
					}
				}
				else
				{
					if (auxiliary->right == NULL)
					{
						// Add new node
						auxiliary->right = new TreeNode(data, this->k);
						// break the loop
						auxiliary = NULL;
					}
					else
					{
						// visit right subtree
						auxiliary = auxiliary->right;
					}
				}
				depth++;
			}
		}
	}
	//  Print the all key of a given node
	void printData(int data[])
	{
		cout << " (";
		for (int i = 0; i < this->k; ++i)
		{
			if (i > 0)
			{
				cout << " , " << data[i];
			}
			else
			{
				cout << " " << data[i];
			}
		}
		cout << ")\n";
	}
	// Display tree node
	void printTree(TreeNode *node)
	{
		if (node != NULL)
		{
			this->printTree(node->left);
			this->printData(node->keys);
			this->printTree(node->right);
		}
	}
	// Compare node and given point
	bool isEquals(int node[], int point[])
	{
		//  When both are same
		for (int i = 0; i < this->k; ++i)
		{
			if (node[i] != point[i])
			{
				return false;
			}
		}
		return true;
	}
	// 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
			{
				cout << " Not Found \n";
			}
		}
		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)
 Not Found

 Given point :  ( 5 , 8)
 Found

 Given point :  ( 5 , 4)
 Not Found
<?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)
					{
						// Add new node
						$auxiliary->left = new TreeNode($data, $this->k);
						// break the loop
						$auxiliary = null;
					}
					else
					{
						// visit left subtree
						$auxiliary = $auxiliary->left;
					}
				}
				else
				{
					if ($auxiliary->right == null)
					{
						// Add new node
						$auxiliary->right = new TreeNode($data, $this->k);
						// break the loop
						$auxiliary = null;
					}
					else
					{
						// visit right subtree
						$auxiliary = $auxiliary->right;
					}
				}
				$depth++;
			}
		}
	}
	//  Print the all key of a given node
	public	function printData( $data)
	{
		echo " (";
		for ($i = 0; $i < $this->k; ++$i)
		{
			if ($i > 0)
			{
				echo " , ". $data[$i];
			}
			else
			{
				echo " ". $data[$i];
			}
		}
		echo ")\n";
	}
	// Display tree node
	public	function printTree($node)
	{
		if ($node != null)
		{
			$this->printTree($node->left);
			$this->printData($node->keys);
			$this->printTree($node->right);
		}
	}
	// Compare node and given point
	public	function isEquals( $node, $point)
	{
		//  When both are same
		for ($i = 0; $i < $this->k; ++$i)
		{
			if ($node[$i] != $point[$i])
			{
				return false;
			}
		}
		return true;
	}
	// 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
			{
				echo " Not Found \n";
			}
		}
		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)
 Not Found

 Given point :  ( 5 , 8)
 Found

 Given point :  ( 5 , 4)
 Not Found
// 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)
					{
						// Add new node
						auxiliary.left = new TreeNode(data, this.k);
						// break the loop
						auxiliary = null;
					}
					else
					{
						// visit left subtree
						auxiliary = auxiliary.left;
					}
				}
				else
				{
					if (auxiliary.right == null)
					{
						// Add new node
						auxiliary.right = new TreeNode(data, this.k);
						// break the loop
						auxiliary = null;
					}
					else
					{
						// visit right subtree
						auxiliary = auxiliary.right;
					}
				}
				depth++;
			}
		}
	}
	//  Print the all key of a given node
	printData(data)
	{
		process.stdout.write(" (");
		for (var i = 0; i < this.k; ++i)
		{
			if (i > 0)
			{
				process.stdout.write(" , " + data[i]);
			}
			else
			{
				process.stdout.write(" " + data[i]);
			}
		}
		process.stdout.write(")\n");
	}
	// Display tree node
	printTree(node)
	{
		if (node != null)
		{
			this.printTree(node.left);
			this.printData(node.keys);
			this.printTree(node.right);
		}
	}
	// Compare node and given point
	isEquals(node, point)
	{
		//  When both are same
		for (var i = 0; i < this.k; ++i)
		{
			if (node[i] != point[i])
			{
				return false;
			}
		}
		return true;
	}
	// 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
			{
				process.stdout.write(" Not Found \n");
			}
		}
		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)
 Not Found

 Given point :  ( 5 , 8)
 Found

 Given point :  ( 5 , 4)
 Not Found
#  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) :
						#  Add new node
						auxiliary.left = TreeNode(data, self.k)
						#  break the loop
						auxiliary = None
					else :
						#  visit left subtree
						auxiliary = auxiliary.left
					
				else :
					if (auxiliary.right == None) :
						#  Add new node
						auxiliary.right = TreeNode(data, self.k)
						#  break the loop
						auxiliary = None
					else :
						#  visit right subtree
						auxiliary = auxiliary.right
					
				
				depth += 1
			
		
	
	#   Print the all key of a given node
	def printData(self, data) :
		print(" (", end = "")
		i = 0
		while (i < self.k) :
			if (i > 0) :
				print(" , ", data[i], end = "")
			else :
				print(" ", data[i], end = "")
			
			i += 1
		
		print(")")
	
	#  Display tree node
	def printTree(self, node) :
		if (node != None) :
			self.printTree(node.left)
			self.printData(node.keys)
			self.printTree(node.right)
		
	
	#  Compare node and given point
	def isEquals(self, node, point) :
		#   When both are same
		i = 0
		while (i < self.k) :
			if (node[i] != point[i]) :
				return False
			
			i += 1
		
		return True
	
	#  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 :
				print(" Not Found ")
			
		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)
 Not Found

 Given point :  (  5 ,  8)
 Found

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

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

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

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

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

				end

				depth += 1
			end

		end

	end

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

			i += 1
		end

		print(")\n")
	end

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

	end

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

			i += 1
		end

		return true
	end

	#  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 
				print(" Not Found \n")
			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)
 Not Found 

 Given point :  ( 5 , 8)
 Found 

 Given point :  ( 5 , 4)
 Not Found 
// 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)
					{
						// Add new node
						auxiliary.left = new TreeNode(data, this.k);
						// break the loop
						auxiliary = null;
					}
					else
					{
						// visit left subtree
						auxiliary = auxiliary.left;
					}
				}
				else
				{
					if (auxiliary.right == null)
					{
						// Add new node
						auxiliary.right = new TreeNode(data, this.k);
						// break the loop
						auxiliary = null;
					}
					else
					{
						// visit right subtree
						auxiliary = auxiliary.right;
					}
				}
				depth += 1;
			}
		}
	}
	//  Print the all key of a given node
	def printData(data: Array[Int]): Unit = {
		print(" (");
		var i: Int = 0;
		while (i < this.k)
		{
			if (i > 0)
			{
				print(" , " + data(i));
			}
			else
			{
				print(" " + data(i));
			}
			i += 1;
		}
		print(")\n");
	}
	// Display tree node
	def printTree(node: TreeNode): Unit = {
		if (node != null)
		{
			this.printTree(node.left);
			this.printData(node.keys);
			this.printTree(node.right);
		}
	}
	// Compare node and given point
	def isEquals(node: Array[Int], point: Array[Int]): Boolean = {
		//  When both are same
		var i: Int = 0;
		while (i < this.k)
		{
			if (node(i) != point(i))
			{
				return false;
			}
			i += 1;
		}
		return true;
	}
	// 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
			{
				print(" Not Found \n");
			}
		}
		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)
 Not Found

 Given point :  ( 5 , 8)
 Found

 Given point :  ( 5 , 4)
 Not Found
// 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)
					{
						// Add new node
						auxiliary!.left = TreeNode(data, self.k);
						// break the loop
						auxiliary = nil;
					}
					else
					{
						// visit left subtree
						auxiliary = auxiliary!.left;
					}
				}
				else
				{
					if (auxiliary!.right == nil)
					{
						// Add new node
						auxiliary!.right = TreeNode(data, self.k);
						// break the loop
						auxiliary = nil;
					}
					else
					{
						// visit right subtree
						auxiliary = auxiliary!.right;
					}
				}
				depth += 1;
			}
		}
	}
	//  Print the all key of a given node
	func printData(_ data: [Int])
	{
		print(" (", terminator: "");
		var i: Int = 0;
		while (i < self.k)
		{
			if (i > 0)
			{
				print(" , ", data[i], terminator: "");
			}
			else
			{
				print(" ", data[i], terminator: "");
			}
			i += 1;
		}
		print(")");
	}
	// Display tree node
	func printTree(_ node: TreeNode? )
	{
		if (node  != nil)
		{
			self.printTree(node!.left);
			self.printData(node!.keys);
			self.printTree(node!.right);
		}
	}
	// Compare node and given point
	func isEquals(_ node: [Int], _ point: [Int])->Bool
	{
		//  When both are same
		var i: Int = 0;
		while (i < self.k)
		{
			if (node[i]  != point[i])
			{
				return false;
			}
			i += 1;
		}
		return true;
	}
	// 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
			{
				print(" Not Found ");
			}
		}
		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)
 Not Found

 Given point :  (  5 ,  8)
 Found

 Given point :  (  5 ,  4)
 Not Found
// 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)
					{
						// Add new node
						auxiliary.left = TreeNode(data, this.k);
						// break the loop
						auxiliary = null;
					}
					else
					{
						// visit left subtree
						auxiliary = auxiliary.left;
					}
				}
				else
				{
					if (auxiliary.right == null)
					{
						// Add new node
						auxiliary.right = TreeNode(data, this.k);
						// break the loop
						auxiliary = null;
					}
					else
					{
						// visit right subtree
						auxiliary = auxiliary.right;
					}
				}
				depth += 1;
			}
		}
	}
	//  Print the all key of a given node
	fun printData(data: Array < Int > ): Unit
	{
		print(" (");
		var i: Int = 0;
		while (i < this.k)
		{
			if (i > 0)
			{
				print(" , " + data[i]);
			}
			else
			{
				print(" " + data[i]);
			}
			i += 1;
		}
		print(")\n");
	}
	// Display tree node
	fun printTree(node: TreeNode ? ): Unit
	{
		if (node != null)
		{
			this.printTree(node.left);
			this.printData(node.keys);
			this.printTree(node.right);
		}
	}
	// Compare node and given point
	fun isEquals(node: Array < Int > , point: Array < Int > ): Boolean
	{
		//  When both are same
		var i: Int = 0;
		while (i < this.k)
		{
			if (node[i] != point[i])
			{
				return false;
			}
			i += 1;
		}
		return true;
	}
	// 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
			{
				print(" Not Found \n");
			}
		}
		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)
 Not Found

 Given point :  ( 5 , 8)
 Found

 Given point :  ( 5 , 4)
 Not Found

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.

Java Code Work

K D tree implementation

Comment

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

New Comment