Quadtree capacity calculator
See how large a fully populated quadtree gets at a given depth, such as 8 cells per side, 64 leaves, 21 internal nodes and 85 nodes in total at depth 3. Use it as the worst-case budget before sizing a node pool. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- Depth
- 3
- Branching factor
- 4
- Levels
- 4
- Cells per side
- 8
- Leaves
- 64
A complete quadtree is the default spatial index when a square region is split into four congruent children at every level. Game collision worlds, GIS tile pyramids, light-probe grids, and image compression trees all share that skeleton. Before you allocate a node pool, size a GPU buffer, or pick a maximum zoom, you need the worst-case census: how many leaves sit at the chosen depth, and how many nodes exist if every branch is populated. This quadtree capacity calculator takes a non-negative integer depth d, treats the root as depth zero, and returns the exact leaf count four to the d, the geometric-series node total of four to the d-plus-one minus one over three, the internal-node remainder, and the two-to-the-d cells along each side of the leaf grid.
How a complete quadtree grows with depth
A quadtree recursively partitions a square, or any two-dimensional axis-aligned box, into four congruent quadrants: northwest, northeast, southwest, and southeast. In a complete, perfectly balanced tree of depth d the root occupies depth zero and every internal node has exactly four children, so the leaves form a regular two-to-the-d by two-to-the-d grid. That is why the leaf count is exactly four to the d — each extra level multiplies the number of cells by four, the branching factor of the tree.
The total number of nodes is the partial geometric series one plus four plus sixteen plus four-to-the-d, which closes to four to the d-plus-one minus one, divided by three. Internal nodes are that total minus the leaves, equivalently four to the d minus one over three. Depth zero is the trivial tree: a single root that is also the only leaf, one cell on a side.
Depth one is the root plus four children: five nodes and four leaves. Depth two is twenty-one nodes and sixteen leaves, the first size many collision systems actually ship. These identities assume a fully populated tree.
Adaptive quadtrees that stop subdividing empty space use fewer nodes, so the figures this calculator returns are the strict upper bound you should budget against.
Where a quadtree capacity figure earns its keep
Graphics and engine teams use a quadtree capacity calculator when they pick a maximum subdivision depth for a two-dimensional broad-phase, a light-probe hierarchy, or a terrain clipmap, because four-to-the-d grows so fast that an extra level is often a four-fold jump in resident nodes. Mapping and GIS pipelines that mint slippy-map tiles or Bing-style quadkeys need the same census to size disk caches and content-delivery prefixes at a given zoom: the leaf grid is two-to-the-d by two-to-the-d, which is the familiar tile count at that zoom.
Image codecs and texture streamers that store a quadtree of blocks use the node total to pre-allocate arenas and to reject a requested depth that would exceed a memory budget. Failed validation does not consume balance. Keep depth inside the documented range, pin the integer counts in tests, and you get reproducible planning numbers for design docs, continuous-integration budgets, and edge workers without standing up a spatial-index sandbox of your own.
What you can do with it
Game and engine node-pool budgets
Pick a maximum broad-phase or terrain depth and read nodes plus leaves before allocating a fixed node arena or a GPU buffer.
Image and texture quadtree arenas
Pre-size a block-tree arena from the node total, and reject a depth whose 4^d leaves would blow the memory budget.
FAQ
How many leaves does a quadtree of depth d have?
A complete quadtree with the root at depth 0 has exactly 4^d leaves, sitting on a 2^d by 2^d grid. Send depth as an integer from 0 through 26.
How is the maximum node count computed?
Nodes are the geometric sum 1 + 4 + 16 + … + 4^d, which equals (4^(d+1) − 1) / 3. Internal nodes are that total minus the leaves.
Does this count an adaptive (sparse) quadtree?
No. The calculator returns the fully populated upper bound. A sparse tree that stops subdividing empty space uses fewer nodes; budget against the complete-tree figures.
Why is depth limited to 26?
Larger depths would lose integer precision in JavaScript numbers.
How do I estimate the memory a quadtree will need?
Multiply the total node count by the size of one node in your own program. The counts cover only the tree's structure, not links between neighbors or the data each node stores, so a depth of 3 means budgeting for 85 nodes.
Related tools
For developers — API access
Everything on this page is available programmatically. This section is for teams who want to wire it into their own systems; everyone else can just use the tool above.
API endpoint
Prefer to automate it? One authenticated POST creates the task; the result comes back by webhook or a signed link. The same capability also runs here on the web, by email and from Telegram — and soon from our app too.
Call it from your stack
curl -X POST https://api.kit.forhosting.com/dev/quadtree-capacity \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"depth":3}'const res = await fetch("https://api.kit.forhosting.com/dev/quadtree-capacity", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"depth": 3
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/dev/quadtree-capacity",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"depth": 3
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/dev/quadtree-capacity", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"depth":3}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"depth":3}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/dev/quadtree-capacity", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Example request
{
"depth": 3
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "dev.quadtree_capacity",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}The API is asynchronous: the call returns a task_id immediately and the result arrives by webhook. Polling is capped at 1 req/s per task.
Pricing
Published price — no tokens, no invented credits. A failed task is never charged.
Limits
max_depth | 26 |
Errors
| HTTP | Code | Meaning |
|---|---|---|
401 | unauthorized | Missing or invalid API key. |
402 | insufficient_balance | Your balance doesn't cover the task price. |
404 | unknown_type | That task type doesn't exist. |
429 | rate_limited | Too many requests. Use the webhook instead of polling. |
Technical notes
How a complete quadtree grows with depth
They do not count neighbour pointers, Morton keys, or payload bytes — only combinatorial structure — which is exactly what you need before choosing a maximum depth.
Input contract, closed-form counts, and the depth cap
Example: depth three yields eight cells on a side, sixty-four leaves, twenty-one internal nodes, and eighty-five nodes in total, because one plus four plus sixteen plus sixty-four is eighty-five. POST a JSON body with the required integer field depth, also accepted as d or max_depth: a whole number from zero through twenty-six inclusive. Missing fields, empty strings, non-integers, negative values, and depths above twenty-six fail with invalid_input naming the field and are not billed. On success the body echoes depth and the constant branching_factor four, then levels equal to depth plus one (the number of node layers from root through leaves), cells_per_side equal to two to the d, leaves equal to four to the d, internal_nodes, nodes, and a short formula string restating the two closed forms. Pair the response with your own memory model if each node carries a payload: multiply nodes by your struct size to estimate a worst-case pool. This endpoint does not allocate a tree, does not traverse points, and does not emit Morton codes; it only evaluates the capacity identities so you can plan before you build.
Integration use cases
Map tile and GIS zoom planning
At zoom d the leaf grid is 2^d by 2^d; use leaves and cells_per_side to size caches, quadkeys, and CDN prefixes.
Technical questions
What does the quadtree capacity calculator cost?
The browser tool is free. API requests use prepaid KIT balance at $0.002 per successful call; invalid input is not billed.