Posted on by Kalkicode
Code Tree

# Find the minimum in K dimensional tree

The problem at hand revolves around finding the minimum value along a given dimension in a K-dimensional tree. A K-dimensional tree, also known as a KD-tree, is a specialized data structure designed for efficiently querying points in multi-dimensional space. In this problem, we aim to construct a KD-tree from a set of points and perform searches to find the minimum value along a specified dimension.

## Problem Statement and Description

Given a set of 2D points, the goal is to construct a KD-tree that efficiently organizes these points. Additionally, the program needs to handle queries to find the minimum value along a specified dimension. This involves traversing the KD-tree and identifying the smallest value along the chosen dimension within a specific subtree.

## Example

Let's consider the following set of 2D 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)
``````

## Idea to Solve

1. Create Tree

Define structures for tree nodes and the KD-tree. The `createTree` function initializes an empty KD-tree.

2. Insertion

Implement the insertion of points into the KD-tree, similar to the previous problem.

3. Minimum Value

Create a recursive function, `findMinimum`, that traverses the KD-tree while considering the specified dimension. At each level of recursion, compare the current node's value along the chosen dimension with the minimum value from its left and right subtrees.

4. Search for Minimum

Implement the `minimum` function that handles queries to find the minimum value along a specified dimension. This function calls the `findMinimum` function and prints the result.

## Pseudocode

The pseudocode for this problem is similar to the previous one with the addition of the `findMinimum` and `minimum` functions:

``````function findMinimum(node, dim, k, depth):
if node is NULL:
return INT_MAX

position = depth % k
if position == dim:
if node.left is NULL:
return node.keys[dim]
return min(node.keys[dim], findMinimum(node.left, dim, k, depth + 1))

return min(node.keys[dim],
min(findMinimum(node.left, dim, k, depth + 1),
findMinimum(node.right, dim, k, depth + 1)))

function minimum(tree, dim):
if tree.root is NULL:
print "Empty Tree"
else if dim < 0 or dim + 1 > tree.k:
print "Invalid Dimension"
else:
ans = findMinimum(tree.root, dim, tree.k, 0)
print "Dimension:", dim
print "Minimum:", ans``````

## Code Solution

``````// C program for
// Find the minimum 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);
}
}
// Returns the minimum of given two values
int minValue(int a, int b)
{
if (a > b)
{
return b;
}
return a;
}
// Recursively finding the minimum of given dimension
int findMinimum(struct TreeNode *node, int dim, int k, int depth)
{
if (node == NULL)
{
// When get a null Node
return INT_MAX;
}
// 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->keys[dim];
}
return minValue(node->keys[dim],
findMinimum(node->left, dim, k, depth + 1));
}
// When position are equal to given a dimension
// Then resultant node can be exists in left or right subtree
return minValue(node->keys[dim],
minValue(findMinimum(node->left, dim, k, depth + 1),
findMinimum(node->right, dim, k, depth + 1)));
}
// 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
{
int ans = findMinimum(tree->root, dim, tree->k, 0);
printf("\n Given Dimension : %d", dim);
printf("\n Minimum is : %d", ans);
}
}
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
}
};
// 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, 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);
minimum(tree, 1);
minimum(tree, 0);
return 0;
}``````

#### Output

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

Given Dimension : 1
Minimum is : 4
Given Dimension : 0
Minimum is : 2``````
``````// Java Program
// Find the minimum 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);
}
}
// Returns the minimum of given two values
public int minValue(int a, int b)
{
if (a > b)
{
return b;
}
return a;
}
// Recursively finding the minimum of given dimension
public int findMinimum(TreeNode node, int dim, int depth)
{
if (node == null)
{
// When get a null Node
return Integer.MAX_VALUE;
}
// 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.keys[dim];
}
return minValue(node.keys[dim], findMinimum(node.left, dim, depth + 1));
}
// When position are equal to given a dimension
// Then resultant node can be exists in left or right subtree
return minValue(node.keys[dim],
minValue(findMinimum(node.left, dim, depth + 1),
findMinimum(node.right, dim, depth + 1)));
}
// 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
{
int ans = findMinimum(this.root, dim, 0);
System.out.print("\n Given Dimension : " + dim );
System.out.print("\n Minimum is : " + ans );
}
}
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
}
};
// 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);
tree.minimum(1);
tree.minimum( 0);
}
}
``````

#### Output

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

Given Dimension : 1
Minimum is : 4
Given Dimension : 0
Minimum is : 2``````
``````// Include namespace system
using System;
using System.Collections;
using System.Linq;
// C# Program
// Find the minimum 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);
}
}
// Returns the minimum of given two values
public int minValue(int a, int b)
{
if (a > b)
{
return b;
}
return a;
}
// Recursively finding the minimum of given dimension
public int findMinimum(TreeNode node, int dim, int depth)
{
if (node == null)
{
// When get a null Node
return int.MaxValue;
}
// 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.keys[dim];
}
return minValue(node.keys[dim],
findMinimum(node.left, dim, depth + 1));
}
// When position are equal to given a dimension
// Then resultant node can be exists in left or right subtree
return minValue(node.keys[dim],
minValue(findMinimum(node.left, dim, depth + 1),
findMinimum(node.right, dim, depth + 1)));
}
// 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
{
int ans = findMinimum(this.root, dim, 0);
Console.Write("\n Given Dimension : " + dim);
Console.Write("\n Minimum is : " + ans);
}
}
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
}
};
// 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);
tree.minimum(1);
tree.minimum(0);
}
}``````

#### Output

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

Given Dimension : 1
Minimum is : 4
Given Dimension : 0
Minimum is : 2``````
``````<?php
// Php Program
// Find the minimum 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);
}
}
// Returns the minimum of given two values
public	function minValue(\$a, \$b)
{
if (\$a > \$b)
{
return \$b;
}
return \$a;
}
// Recursively finding the minimum of given dimension
public	function findMinimum(\$node, \$dim, \$depth)
{
if (\$node == null)
{
// When get a null Node
return PHP_INT_MAX;
}
// 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->keys[\$dim];
}
return \$this->minValue(\$node->keys[\$dim],
\$this->findMinimum(\$node->left, \$dim, \$depth + 1));
}
// When position are equal to given a dimension
// Then resultant node can be exists in left or right subtree
return \$this->minValue(\$node->keys[\$dim],
\$this->minValue(\$this->findMinimum(\$node->left,
\$dim, \$depth + 1),
\$this->findMinimum(\$node->right, \$dim, \$depth + 1)));
}
// 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
{
\$ans = \$this->findMinimum(\$this->root, \$dim, 0);
echo "\n Given Dimension : ". \$dim;
echo "\n Minimum is : ". \$ans;
}
}
}

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)
);
// Get the number of elements
\$n = count(\$data);
// Insert all given nodes
for (\$i = 0; \$i < \$n; ++\$i)
{
\$tree->insert(\$data[\$i]);
}
/*
(8, 9)
/      \
(7,6)    (11,12)
\      /    \
(3,9)(9,4)  (10,13)
/        \
(2,8)      (14,8)
-----------------
Developed tree

*/
echo "\n Tree Nodes\n";
\$tree->printTree(\$tree->root);
\$tree->minimum(1);
\$tree->minimum(0);
}
main();``````

#### Output

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

Given Dimension : 1
Minimum is : 4
Given Dimension : 0
Minimum is : 2``````
``````// Node Js Program
// Find the minimum 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);
}
}
// Returns the minimum of given two values
minValue(a, b)
{
if (a > b)
{
return b;
}
return a;
}
// Recursively finding the minimum of given dimension
findMinimum(node, dim, depth)
{
if (node == null)
{
// When get a null Node
return Number.MAX_VALUE;
}
// 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.keys[dim];
}
return this.minValue(node.keys[dim], this.findMinimum(node.left, dim, depth + 1));
}
// When position are equal to given a dimension
// Then resultant node can be exists in left or right subtree
return this.minValue(node.keys[dim], this.minValue(this.findMinimum(node.left, dim, depth + 1), this.findMinimum(node.right, dim, depth + 1)));
}
// 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 ans = this.findMinimum(this.root, dim, 0);
process.stdout.write("\n Given Dimension : " + dim);
process.stdout.write("\n Minimum is : " + ans);
}
}
}

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]
];
// 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);
tree.minimum(1);
tree.minimum(0);
}
main();``````

#### Output

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

Given Dimension : 1
Minimum is : 4
Given Dimension : 0
Minimum is : 2``````
``````import sys
#  Python 3 Program
#  Find the minimum 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)

#  Returns the minimum of given two values
def minValue(self, a, b) :
if (a > b) :
return b

return a

#  Recursively finding the minimum of given dimension
def findMinimum(self, node, dim, depth) :
if (node == None) :
#  When get a null Node
return sys.maxsize

#  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.keys[dim]

return self.minValue(node.keys[dim],
self.findMinimum(node.left, dim, depth + 1))

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

#  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 :
ans = self.findMinimum(self.root, dim, 0)
print("\n Given Dimension : ", dim, end = "")
print("\n Minimum is : ", ans, end = "")

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]
]
#  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)
tree.minimum(1)
tree.minimum(0)

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

#### Output

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

Given Dimension :  1
Minimum is :  4
Given Dimension :  0
Minimum is :  2``````
``````#  Ruby Program
#  Find the minimum 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

#  Returns the minimum of given two values
def minValue(a, b)
if (a > b)
return b
end

return a
end

#  Recursively finding the minimum of given dimension
def findMinimum(node, dim, depth)
if (node == nil)
#  When get a null Node
return (2 ** (0. size * 8 - 2))
end

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

return self.minValue(node.keys[dim],
self.findMinimum(node.left, dim, depth + 1))
end

#  When position are equal to given a dimension
#  Then resultant node can be exists in left or right subtree
return self.minValue(node.keys[dim],
self.minValue(self.findMinimum(node.left, dim, depth + 1),
self.findMinimum(node.right, dim, depth + 1)))
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
ans = self.findMinimum(self.root, dim, 0)
print("\n Given Dimension : ", dim)
print("\n Minimum is : ", ans)
end

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]
]
#  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)
tree.minimum(1)
tree.minimum(0)
end

main()``````

#### Output

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

Given Dimension : 1
Minimum is : 4
Given Dimension : 0
Minimum is : 2``````
``````// Scala Program
// Find the minimum 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);
}
}
// Returns the minimum of given two values
def minValue(a: Int, b: Int): Int = {
if (a > b)
{
return b;
}
return a;
}
// Recursively finding the minimum of given dimension
def findMinimum(node: TreeNode, dim: Int, depth: Int): Int = {
if (node == null)
{
// When get a null Node
return Integer.MAX_VALUE;
}
// Get dimension position
var position: Int = depth % this.k;
if (position == dim)
{
// When position are equal to given a dimension
if (node.left == null)
{
// Returns the current dimension
return node.keys(dim);
}
return this.minValue(node.keys(dim),
this.findMinimum(node.left, dim, depth + 1));
}
// When position are equal to given a dimension
// Then resultant node can be exists in left or right subtree
return this.minValue(node.keys(dim),
this.minValue(this.findMinimum(node.left, dim, depth + 1),
this.findMinimum(node.right, dim, depth + 1)));
}
// 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 ans: Int = this.findMinimum(this.root, dim, 0);
print("\n Given Dimension : " + dim);
print("\n Minimum is : " + ans);
}
}
}
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)
);
// 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);
tree.minimum(1);
tree.minimum(0);
}
}``````

#### Output

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

Given Dimension : 1
Minimum is : 4
Given Dimension : 0
Minimum is : 2``````
``````// Swift 4 Program
// Find the minimum 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);
}
}
// Returns the minimum of given two values
func minValue(_ a: Int, _ b: Int)->Int
{
if (a > b)
{
return b;
}
return a;
}
// Recursively finding the minimum of given dimension
func findMinimum(_ node: TreeNode? , _ dim : Int, _ depth: Int)->Int
{
if (node == nil)
{
// When get a null Node
return Int.max;
}
// 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!.keys[dim];
}
return self.minValue(node!.keys[dim],
self.findMinimum(node!.left, dim, depth + 1));
}
// When position are equal to given a dimension
// Then resultant node can be exists in left or right subtree
return self.minValue(node!.keys[dim],
self.minValue(self.findMinimum(node!.left, dim, depth + 1),
self.findMinimum(node!.right, dim, depth + 1)));
}
// 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 ans: Int = self.findMinimum(self.root, dim, 0);
print("\n Given Dimension : ", dim, terminator: "");
print("\n Minimum is : ", ans, terminator: "");
}
}
}
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]
];
// 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);
tree.minimum(1);
tree.minimum(0);
}
main();``````

#### Output

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

Given Dimension :  1
Minimum is :  4
Given Dimension :  0
Minimum is :  2``````
``````// Kotlin Program
// Find the minimum 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);
}
}
// Returns the minimum of given two values
fun minValue(a: Int, b: Int): Int
{
if (a > b)
{
return b;
}
return a;
}
// Recursively finding the minimum of given dimension
fun findMinimum(node: TreeNode ? , dim : Int, depth: Int): Int
{
if (node == null)
{

// When get a null Node
return Integer.MAX_VALUE;
}
// Get dimension position
var position: Int = depth % this.k;
if (position == dim)
{
// When position are equal to given a dimension
if (node.left == null)
{

// Returns the current dimension
return node.keys[dim];
}
return this.minValue(node.keys[dim],
this.findMinimum(node.left, dim, depth + 1));
}

// When position are equal to given a dimension
// Then resultant node can be exists in left or right subtree
return this.minValue(node.keys[dim],
this.minValue(this.findMinimum(node.left, dim, depth + 1),
this.findMinimum(node.right, dim, depth + 1)));
}
// 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 ans: Int = this.findMinimum(this.root, dim, 0);
print("\n Given Dimension : " + dim);
print("\n Minimum is : " + ans);
}
}
}
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));
// 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);
tree.minimum(1);
tree.minimum(0);
}``````

#### Output

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

Given Dimension : 1
Minimum is : 4
Given Dimension : 0
Minimum is : 2``````

## Resultant Output Explanation

The code constructs a KD-tree from the given 2D points and prints the elements of the tree using in-order traversal. It then uses the `minimum` function to find the minimum values along dimensions 1 and 0.

• For dimension 1, the minimum value is 4.
• For dimension 0, the minimum value is 2.

These results are consistent with the tree structure and the points' values.

## Time Complexity

• The minimum value search operation takes O(log n) time on average, where n is the number of nodes in the tree.

## Comment

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

Categories
Relative Post