I am trying to understand how KD-tree works when we insert a node and how it splits the xy plane, please. Below $[5, 4]$ splits the xy-plane into left and right parts while $[2,6]$ splits it into top and bottom. Why don't we say that $[2,6]$ again splits the space into left and right?

enter image description here


1 Answer 1


The root will choose the split in one direction (in your case, (5,4) creates a vertical split). Then any nodes at the next level in your tree will split horizontally, then the nodes in the next level of the tree will split vertically again.

If you are only splitting one way - like you suggest with only vertical splits - then you are essentially storing everything in a binary search tree with respect to the x-coordinate (and the data structure completely ignores the y-coordinate). But to make use of both coordinates and create a kind of two-dimensional binary search tree, this alternating levels thing is done.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.