Build a quadtree over a square grid

A quadtree splits a square region of the plane into four quadrants, recursively: every node is either a leaf or has exactly four children. Build one yourself, in two versions. First from a square grid of values, then as an index of 2D points that supports inserts and range queries.

Part 1: quadtree from a grid

Unless you agree on a different interface with the interviewer, assume:

• build(grid: list[list[int]]) -> Node — grid is n x n. If every cell of a region holds the same value, the region is a leaf with that value. Otherwise split it into top-left, top-right, bottom-left and bottom-right quadrants and recurse. Values are any integers, not only 0 and 1.

Example, writing a leaf as its value and an inner node as a list of its four children in that order:

grid = [[1, 1, 2, 2],
        [1, 1, 2, 2],
        [3, 3, 4, 5],
        [3, 3, 6, 4]]

build(grid)  ->  [1, 2, 3, [4, 5, 6, 4]]

Part 2: quadtree of points

• QuadTree(x_min, y_min, x_max, y_max, capacity) — covers the given rectangle; a leaf holds at most capacity points before it splits into four.
• insert(x: float, y: float) -> bool — adds a point; returns False if it lies outside the root's region.
• query(x1, y1, x2, y2) -> list[tuple[float, float]] — every stored point inside the rectangle, borders included.

qt = QuadTree(0, 0, 100, 100, capacity=2)
insert(10, 10); insert(20, 20); insert(80, 80)   # the root splits on the third insert
query(0, 0, 50, 50)    ->  [(10, 10), (20, 20)]           # in any order
insert(150, 10)        ->  False

Constraints

• Part 1: n is a power of two unless you agree otherwise.
• Part 2: points may repeat, and a point may fall exactly on a dividing line.

Clarifying questions

• Is the grid side always a power of two? If not, how are uneven quadrants split?
• Which quadrant owns a point that lies exactly on a split line?
• How should duplicate points be handled? Many identical points can make a leaf split forever.
• Is there a maximum depth?

What a strong answer covers

• Part 1: the recursive build, and its cost. Checking each region naively is O(n² log n); building bottom-up and merging four equal leaves is O(n²).
• Part 2: a consistent rule for points on boundaries, splitting on capacity, and a depth limit or duplicate handling so the tree cannot recurse forever.
• Range queries that skip quadrants not intersecting the rectangle, with their typical and worst-case cost.
• Tests: a uniform grid (one leaf), a grid where every cell differs, boundary points, duplicates.

Follow-ups

• Find the nearest stored point to a query location.
• Support deleting points and merging quadrants that become sparse.
• Store latitude and longitude for a city's drivers. What changes, and when would you prefer a geohash or a fixed grid?