Recently I went to a gym with a friend of mine and we had a chat about QuadTrees and k-d trees (yeah… don’t invite software engineers to your party – they will spoil everything). He asked me to explain what QuadTree is, and I said that it’s like binary tree just with four children instead of two. He then said it must be a variety of k-d tree. “Well…” – thought I – “probably, but I don’t know”. He explained that k-d trees as used to break k-dimensional space, which seemed reasonable as QuadTree is used to break two-dimensional space. Below are definitions of the two from wikipedia as well as some of context and my drawings.

QuadTree

A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees […] are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions.

https://en.wikipedia.org/wiki/Quadtree

Something like QuadTree could be used to compress images or to break a map of uneven density into regions where each node would have similar density.

For breaking a map, you can think of a designing a system that handles storage of information about restaurants and other points of interest. You would like to look up the information using your location on a map. Obviously downtown of a big city would have high density of these places and you might not want to show all of them to your user. So you would break you map into more quadrants few levels down, but on the outskirts you might have only few nodes that cover larger areas.

I just drew this process of compressing an image below. What you see on the bottom-left corner (SW) is an image, which was broken on bottom-right (SE) into 4 quadrants, each of which was broken into some more, but the moment either black or white occupied entire square the process stopped. Top-right (NE) is visualization of a compressed image (not too nice), and top-left (NW) is the QuadTree with some of the leafs pointing to their position on compressed image, which needed only 67 nodes and depending on how we store the data it could be insanely small amount of data required.

k-d tree

[…] k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches).

https://en.wikipedia.org/wiki/K-d_tree

I didn’t draw anything for the k-d tree, but on very high level the idea is similar of breaking the space and going few levels down (there exists a generalization called binary space partitioning). With k-d tree the space is broken into TWO half-spaces by one of the dimensions instead of FOUR. Say, if it was “z”, then all children to the left will have “z” of smaller value than parent, and all to the right will have greater than parent. What I find interesting about k-d tree implementation is assigning axis to levels (root “x”, its children “y”, their children “z”, next level would be “x” again and so on for 3-dimensional space).

Conclusion

Don’t be like me, read a bit about these fascinating data structures and their application and who knows, you might be able to strike a great conversation in your local gym! :)