Construct Quad Tree

Sanjeev SharmaSanjeev Sharma
2 min read

Advertisement

Problem

Construct a quad tree from an n×n binary matrix. If a region is all-same, it's a leaf. Otherwise split into 4.

Solutions

# Python
def construct(grid):
    n = len(grid)
    def build(r, c, size):
        val = grid[r][c]
        uniform = all(grid[r+i][c+j] == val for i in range(size) for j in range(size))
        if uniform:
            return Node(val == 1, True)
        half = size // 2
        node = Node(True, False)
        node.topLeft     = build(r,        c,        half)
        node.topRight    = build(r,        c + half, half)
        node.bottomLeft  = build(r + half, c,        half)
        node.bottomRight = build(r + half, c + half, half)
        return node
    return build(0, 0, n)
// C++
Node* build(vector<vector<int>>& g, int r, int c, int sz) {
    int v = g[r][c];
    bool uniform = true;
    for (int i=r;i<r+sz&&uniform;i++) for(int j=c;j<c+sz;j++) if(g[i][j]!=v){uniform=false;break;}
    if (uniform) return new Node(v==1, true);
    int h = sz/2;
    auto node = new Node(true, false);
    node->topLeft=build(g,r,c,h); node->topRight=build(g,r,c+h,h);
    node->bottomLeft=build(g,r+h,c,h); node->bottomRight=build(g,r+h,c+h,h);
    return node;
}
Node* construct(vector<vector<int>>& grid) { return build(grid,0,0,grid.size()); }
// Java
public Node construct(int[][] grid) { return build(grid, 0, 0, grid.length); }
Node build(int[][] g, int r, int c, int sz) {
    int v = g[r][c]; boolean uni = true;
    outer: for(int i=r;i<r+sz;i++) for(int j=c;j<c+sz;j++) if(g[i][j]!=v){uni=false;break outer;}
    if (uni) return new Node(v==1,true);
    int h=sz/2; Node n=new Node(true,false);
    n.topLeft=build(g,r,c,h); n.topRight=build(g,r,c+h,h);
    n.bottomLeft=build(g,r+h,c,h); n.bottomRight=build(g,r+h,c+h,h);
    return n;
}
// JavaScript
function construct(grid) {
    const n = grid.length;
    function build(r, c, size) {
        const val = grid[r][c];
        let uniform = true;
        outer: for (let i=r;i<r+size;i++) for(let j=c;j<c+size;j++) if(grid[i][j]!==val){uniform=false;break outer;}
        if (uniform) return new Node(val===1, true);
        const h = size>>1;
        const node = new Node(true, false);
        node.topLeft=build(r,c,h); node.topRight=build(r,c+h,h);
        node.bottomLeft=build(r+h,c,h); node.bottomRight=build(r+h,c+h,h);
        return node;
    }
    return build(0, 0, n);
}

Complexity

  • Time: O(n^2 log n), Space: O(log n) recursion

Advertisement

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro