Skip to main content

K dimensional tree insertion

Here given code implementation process.

// 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
K D tree implementation
Last updated on by Kalkicode




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