Abstract to Go: Quad Trees

While going through important concepts for system design interviews, I came across quad trees, a data structure with numerous applications. But its always better to know the problem it solves.

Pre-requisites

A base level understanding of trees and tree-traversal would help you get a better understanding of the code.

Introduction

Let's talk about a 2-dimensional multiplayer game. We have a hilly landscape with two tanks on the opposite side. trying to destroy each other. For every miss, the bomb will probably explode on land, and hence a crater will be created. Let's assume for now that the blast is circular in nature. If we don't have to worry about the graphics, how do we change the state of the area to represent an empty space that used to be land?

Let's take another example. You have to create an application that shares how many people live in a radius of 5km with you at the centre.

Quad Tree

In such situations, data structures like quad trees perform really well. Both the map and the 2D game of tank can be visualised as a matrix of size n.

The idea is pretty simple. Calculate the total value for the whole matrix. In our case, let's say the world population is 8 billion. So we have a node with a value of 8 billion. Now divide the matrix (or map) into four nodes: North West, North East, South West, and South East. Calculate the population of all these nodes. Connect these nodes to the root. What you did on the root, now do for each of the nodes.
Keep doing this until you find a depth that is appropriate for the use case. Below is the diagram that will help you visualise the same.

Similarly, for the tank game with explosives, we can divide the 2D scenery into smaller segments, up to a depth that may be equal to the minimum blast radius of a missile in the game. The smallest cell (from the maximum depth) can be marked as equal to 1. All the non-land areas can be marked zero. The higher depth of a quad tree will lead to more realistic explosions. Below is an example of the same. Each cell here can hold a value of 4. There is another depth level that is not shown for clarity. Each of those cells will have a value of 1. You can see that around the border between the land and non-land regions, the boxes have values of 1, 2, and 3, meaning that in those boxes there are 1, 2, or 3 land segments.

Implementation

Now this is the easy part. Let's skip the part where we have to map these problems onto a 2D matrix.

What should we be able to do with this quad tree?

• Find Regions: Get all those areas with population X
• Add: As the population regularly increases, the values in the quad tree should be updated as well. The same can be used for the other example. The only difference would be that we would pass negative values instead.

Quad Tree Structure

The structure, in many ways, will be similar to a tree. In each node, we have to save the coordinates, the value of the quadrant, and the depth level.
For the coordinates, we need to know the minimum and maximum of the row and column values.
This is how the structure may look:

type QuadTree struct {
    lvl      int
    val      int
    x        [2]int // start and end index of matrix row
    y        [2]int // start and end index of matrix column
    children []*QuadTree
}

Initialising the Quad Tree

So we already have all the information laid out on a 2D matrix.
These are the steps we would have to follow :

1. Calculate Sum of each cell in the matrix
2. Create a node and set the sum. Set Depth level
3. Split matrix into four parts
4. Repeat steps 1 to 3 for each quadrant until the specified depth level is achieved.

This is what the code will look like

func New(arr [][]int, dp int) *QuadTree {

    var newquadtree func(arr [][]int, depth int, lc, rc, tr, br int) *QuadTree
    newquadtree = func(arr [][]int, depth int, lc, rc, tr, br int) *QuadTree {
        if lc+1 == rc || tr+1 == br {
            return nil
        }
        sum := 0
        for i := tr; i < br; i++ {
            for j := lc; j < rc; j++ {
                sum += arr[i][j]
            }
        }
        qt := &QuadTree{
            val: sum,
            x:   [2]int{tr, br},
            y:   [2]int{lc, rc},
            lvl: dp - depth,
        }
        if depth == 0 {
            return qt
        }
        midR := tr + (br-tr)/2
        midC := lc + (rc-lc)/2
        qt.children = append(qt.children, newquadtree(arr, depth-1, lc, midC, tr, midR))
        qt.children = append(qt.children, newquadtree(arr, depth-1, lc, midC, midR, br))
        qt.children = append(qt.children, newquadtree(arr, depth-1, midC, rc, tr, midR))
        qt.children = append(qt.children, newquadtree(arr, depth-1, midC, rc, midR, br))
        return qt
    }

    return newquadtree(arr, dp, 0, len(arr[0]), 0, len(arr))
}

Here I am recursively calling the quadTree generation until a specified depth can be reached or if the current matrix cannot be divided into further quadtrants.

Find Regions

We will again be using DFS to find out which regions have values passed to the function. The aim here is to find the smallest quadrant that holds the value. These are the main things we have to make sure to check

• If current nodes value < target, dont traverse
• If all child quadrants hold a value < target, the current node is the smallest quadrant that holds a value >= target, so append the current node to the list of results.
• If the child quadrant holds value >= target, traverse the child quadrant.

This is how the code may look like :

func (qt QuadTree) FindRegions(value int) []*QuadTree {
    arr := []*QuadTree{}
    var dfs func(node *QuadTree, depth int)
    dfs = func(node *QuadTree, depth int) {
        if node == nil {
            return
        }
        if node.val < value {
            return
        }
        flag := false
        for _, child := range node.children {
            fmt.Println("For ", node, "child value::", child.val)
            if child.val > value {

                dfs(child, depth+1)
                flag = true
            }
        }

        if !flag {
            fmt.Println("Flag", flag, "for ", node)
            arr = append(arr, node)
        }
    }
    dfs(&qt, 0)
    for _, v := range arr {
        fmt.Println(v.val, v.x, v.y)
    }
    return arr
}

Add Value to a region

Here we may be asked to increase the value of a particular region. We would need to recognise the value of all the parents in that particular region.
This is pretty straight forward to figure out. Keep on traversing the quadrant that holds the region, and keep incrementing these quadrants with the value.

This is what the code may look like

func (qt *QuadTree) Add(value, x, y int) {
    var dfs func(node *QuadTree)
    dfs = func(node *QuadTree) {
        if node == nil {
            return
        }
        node.val += value
        for _, n := range node.children {
            if n == nil {
                continue
            }
            if n.x[0] <= x && n.x[1] >= x {
                if n.y[0] <= y && n.y[1] >= y {
                    dfs(n)
                }
            }

        }
    }
    dfs(qt)
}

And that's it! Remember, there are a lot more properties of quadtrees, and only the basics are covered. you can find the code for the implementation here. Do you believe the algorithm can be further optimised? Let me know.