Quad Tree

In a geohash structure, a map is divided into 4 different squares, for example:

Which can then be represented as a quad tree:

Pseudo

package datastructures;

class Node {
  public boolean val;
  public boolean isLeaf;
  public Node topLeft;
  public Node topRight;
  public Node bottomLeft;
  public Node bottomRight;


  public Node() {
    this.val = false;
    this.isLeaf = false;
    this.topLeft = null;
    this.topRight = null;
    this.bottomLeft = null;
    this.bottomRight = null;
  }

  public Node(boolean val, boolean isLeaf) {
    this.val = val;
    this.isLeaf = isLeaf;
    this.topLeft = null;
    this.topRight = null;
    this.bottomLeft = null;
    this.bottomRight = null;
  }

  public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
    this.val = val;
    this.isLeaf = isLeaf;
    this.topLeft = topLeft;
    this.topRight = topRight;
    this.bottomLeft = bottomLeft;
    this.bottomRight = bottomRight;
  }
};

public class QuadTree {
  public static void main(String[] args) {
    QuadTree quadTree = new QuadTree();
    Node node = quadTree.construct(new int[][] {{0, 1}, {1, 0}});
    System.out.println(node);
  }
  public Node construct(int[][] grid) {
    Node root = construct(grid, 0, grid[0].length - 1, 0, grid.length - 1);
    return root;
  }

  private Node construct(int[][] grid, int colStart, int colEnd, int rowStart, int rowEnd) {
    if (!withinBoundary(grid, colStart, colEnd, rowStart, rowEnd)) {
      return null;
    }

    if (colStart == colEnd && rowStart == rowEnd) {
      // at the smallest unit of the grid
      return new Node(grid[rowStart][colStart] == 1, true);
    }

    Node root = new Node(false, false);
    int halfCol = (colStart + colEnd) / 2; // 0
    int halfRow = (rowStart + rowEnd) / 2; // 0

    root.topLeft = construct(grid, colStart, halfCol, rowStart, halfRow); // 0 -> 0, 0 -> 0
    root.topRight = construct(grid, halfCol + 1, colEnd, rowStart, halfRow); // 1 -> 1, 0 -> 0

    root.bottomLeft = construct(grid, colStart, halfCol, halfRow + 1, rowEnd); // 0 -> 0, 1 -> 1
    root.bottomRight = construct(grid, halfCol + 1, colEnd, halfRow + 1, rowEnd); // 1 -> 1, 1 -> 1

    return root;
  }

  private boolean withinBoundary(int[][] grid, int colStart, int colEnd, int rowStart, int rowEnd) {
    return !(colStart < 0 || rowStart < 0 || colEnd < 0 || rowEnd < 0 || rowStart >= grid.length || rowEnd >= grid.length || colStart >= grid[0].length || colEnd >= grid[0].length);
  }
}

Use cases

Find nearby 100 restaurants

Divide the plannet into 4 quarters like

[0, 1]
[1, 0]

Each of that 4 quarter we divide further again. which can result into something like

[ 
   01, 11
   10, 10
]

And we keep doing like this. When we want to search for nearby 100 restaurants, we can simply do something like this:

SELECT * FROM geohash_index WHERE geohash LIKE `01%`