k-d tree is a binary-tree based data structure. It can be used for data which is k-dimensional.

**What do we mean by k-dimensional?**

You may have heard of 2-D and 3-D. Similarly, we have higher dimension space.

**Why do we need k-d tree?**

Using k-d tree we can partition a k-dimensional space into regions. This allows for efficient searching. It’s used in computer graphics and nearest neighbour searches.

**How it works?**

Let us consider a 2-D dataset. A point in this can be represented as <X,Y>

**Constructing a k-d tree**

We follow these steps to construct the tree.

1. Select a dimension and project all points along that. Example: Project all points along X-axis.

2. Take the mean of points generated along X-axis. Let’s call it X_M

3. Split using the mean. If a point X1 is < X_M then it goes to the left sub-tree else right.

4. Repeat steps 1-3 for all dimensions.

By constructing this tree we have partitioned the space into smaller regions. Given a new query point we can traverse through the Tree to find an appropriate region.