Find the minimum in K dimensional tree

Here given code implementation process.

// 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)
				{
					// 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);
	}
}
// 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)
                    {
                        // 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);
        }
    }
  // 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)
					{
						// Add new node
						auxiliary.left = new TreeNode(data, this.k);
						// break the loop
						auxiliary = null;
					}
					else
					{
						// visit left subtree
						auxiliary = auxiliary.left;
					}
				}
				else
				{
					if (auxiliary.right == null)
					{
						// Add new node
						auxiliary.right = new TreeNode(data, this.k);
						// break the loop
						auxiliary = null;
					}
					else
					{
						// visit right subtree
						auxiliary = auxiliary.right;
					}
				}
				depth++;
			}
		}
	}
	//  Print the all key of a given node
	public void printData(int[] data)
	{
		Console.Write(" (");
		for (int i = 0; i < this.k; ++i)
		{
			if (i > 0)
			{
				Console.Write(" , " + data[i]);
			}
			else
			{
				Console.Write(" " + data[i]);
			}
		}
		Console.Write(")\n");
	}
	// Display tree node
	public void printTree(TreeNode node)
	{
		if (node != null)
		{
			printTree(node.left);
			printData(node.keys);
			printTree(node.right);
		}
	}
	// 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)
					{
						// 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);
		}
	}
	// 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)
					{
						// 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);
		}
	}
	// 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) :
						#  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)
		
	
	#  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_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

	#  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)
					{
						// 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);
		}
	}
	// 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)
					{
						// 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);
		}
	}
	// 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)
					{
						// 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);
		}
	}
	// 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


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







© 2021, kalkicode.com, All rights reserved