> Interview Breeze

How to Implement a Quadtree in Python

What is a Quadtree?

A Quadtree is a data structure that allows two dimensional data, such as images or matrices, to be represented and traversed as a tree. The basic structure of a Quadtree is a node that has 4 children nodes, upper left, upper right, bottom left, and bottom right (it is also common to see the terms northeast, northwest, southeast, and southwest used for the children nodes.) Each of these child nodes references a region of the 2 dimensional data.

Why use a Quadtree?

There are a number of benefits to representing 2 dimensional data as a tree. One example is when we need to search or traverse areas of a tree for updating and want to be able to do it in logarithmic time. Quadtrees are also a powerful structure that are commonly used in graphics programming and development.

Implementing a Quadtree

To make our life easy, we will implement a helper matrix class:

from collections import namedtuple

MatrixShape = namedtuple('MatrixShape', 'width height')

class Matrix(object):

    # data is a list of lists
    def __init__(self, data):
        self.data = data

    def shape(self):
        if not self.data:
            return MatrixShape(width=0, height=0)
        return MatrixShape(
            len(self.data[0]),
            len(self.data)
        )


    # getter for indexing like an array

    def __getitem__(self, key):
        return self.data[key]

    # return a sub matrix from x1,y1 to x2,y2 (not including x2,y2)
    def sub(self, x1, y1, x2, y2):

        if x1 < 0 or y1 < 0:
            raise ValueError("X1,Y1 must be positive")

        if x1 > x2 or y1 > y2: 
            raise ValueError("X1,Y1 must be smaller than X2,Y2")

        mShape = self.shape();
        max_x2 = x2 if x2 < mShape.width else mShape.width - 1
        max_y2 = y2 if y2 < mShape.height else mShape.height - 1

        return Matrix(
            [
                [self.data[row][col] for col in range(x1, max_x2 + 1)] 
                for row in range(y1, max_y2 + 1)
            ]
        )

    def __str__(self):
        return "%s" % self.data

Using this matrix class, we can implement our QuadTree trivially. When implementing a Quadtree, in order for the tree to have the same depth for all leaf nodes, the matrix needs to have a number of cells equal to a power of 2 and have an equal width and height. It is possible to have a Quadtree of different depths, but for our implementation we will add some simple error handling and require a square matrix with an even number of rows and columns so that we can guarantee the tree is the same height at all leaf nodes.

class QuadTree(object):

    def __init__(self, matrix):

        if not matrix:
            raise ValueError("Matrix cannot be None or empty")

        self.leafNode = False
        self.value = None

        mShape = matrix.shape()

        if mShape.width == 1 and mShape.height == 1:
            self.leafNode = True
            self.value = matrix[0][0]
            return

        if mShape.width == 0 or (mShape.width & (mShape.width - 1)) != 0:
            raise ValueError("Matrix size must be a power of 2")

        if mShape.width != mShape.height:
            raise ValueError("Matrix must have same width and height")

        self.size = mShape.width
        quadSize = self.size / 2

        self.upperLeft = QuadTree(matrix.sub(0,0,quadSize-1,quadSize-1));
        self.bottomLeft = QuadTree(matrix.sub(0,quadSize,quadSize-1,(quadSize*2)-1));
        self.upperRight = QuadTree(matrix.sub(quadSize,0,(quadSize*2)-1,quadSize-1));
        self.bottomRight = QuadTree(matrix.sub(quadSize,quadSize,(quadSize*2)-1,(quadSize*2)-1));

    def __str__(self, level=0):
        padding = " " * level
        if self.leafNode:
            return "%s+ %s" % (padding, self.value)
        else:
            s = []
            s.append("%s+ ul\n%s" % (padding, self.upperLeft.__str__(level + 1)))
            s.append("%s+ ur\n%s" % (padding, self.upperRight.__str__(level + 1)))
            s.append("%s+ bl\n%s" % (padding, self.bottomLeft.__str__(level + 1)))
            s.append("%s+ br\n%s" % (padding, self.bottomRight.__str__(level + 1)))
            return "\n".join(s)

Using the above classes, if we were to instantiate a Quadtree and print it out, we would be able to see visually how a Quadtree would represent the matrix:

mat = Matrix([range(4) for x in range(4)])
tree = QuadTree(mat)
print(tree)

The output for the above code would look like so:

+ ul
 + ul
  + 0
 + ur
  + 1
 + bl
  + 0
 + br
  + 1
+ ur
 + ul
  + 2
 + ur
  + 3
 + bl
  + 2
 + br
  + 3
+ bl
 + ul
  + 0
 + ur
  + 1
 + bl
  + 0
 + br
  + 1
+ br
 + ul
  + 2
 + ur
  + 3
 + bl
  + 2
 + br
  + 3

You may also want to read:

Discerning a tree from a graph

Write a function that takes a node and returns True if the node is part of a tree or False if it's part of a graph.

Read More >>
Depth First Search

Depth first search (sometimes referred to as DFS) is an algorithm for traversing a graph or tree.

Read More >>
Binary Tree Column Printer

Given binary tree, write a function to print its values in column order, from the bottom to top. You can assume that there will be no collisions, in which 2 nodes would occupy the same row and column.

Read More >>