Recursion tree node count calculator
Count the nodes of a divide-and-conquer recursion tree level by level: two half-size subproblems starting from 16 give 5 levels of 1, 2, 4, 8 and 16 nodes, 31 in all, 16 of them leaves. Check homework without drawing the tree. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- Branching factor
- 2
- Shrink ratio
- 2
- Input size
- 16
- Level count
- 5
- Tree height
- 4
- Total nodes
- 31
- Leaf nodes
- 16
Divide-and-conquer recurrences of the form T of n equals a times T of n over b plus non-recursive work appear in every algorithms course when merge sort, binary space partitions, or multiway recursion are drawn as trees. Students need a trustworthy count of how many nodes sit at each level and how deep the tree grows before subproblems hit the base case. This recursion tree node count calculator accepts the branching factor a, the shrink ratio b, and the root input size n, walks the tree until subproblem size is at most one, and returns level count, tree height, total and leaf node counts, the per-level node sequence, subproblem sizes, and two fractional work distributions. One distribution assumes unit cost per node; the other assumes work proportional to subproblem size, matching the usual merge-sort style picture where every full level still does linear work in n.
What a recursion tree counts and how levels are defined
A recursion tree is a picture of every subproblem created by a divide-and-conquer algorithm whose time satisfies T of n equals a times T of n over b plus f of n. The root represents the original instance of size n. Each internal node has exactly a children, each solving a problem whose size is the parent size divided by b.
Levels are numbered from zero at the root. At level i there are a to the power i nodes, and each of those nodes has subproblem size n divided by b to the power i, provided sizes stay real and positive. The walk continues while the current size is strictly greater than one; the first level whose size is less than or equal to one is kept as the leaf level of base cases, then the walk stops.
That convention matches the textbook stop condition of solving constant-size inputs directly. Tree height is level count minus one, the number of edges on a root-to-leaf path. Leaf nodes equal a raised to the height when sizes hit one on an exact power boundary, and more generally equal the node count on the last recorded level.
Internal nodes are total nodes minus leaves. For branching factor one the tree is a single spine of length equal to the number of successive divisions until size is at most one.
Where counting recursion tree nodes helps
Algorithms courses and tutoring platforms use a recursion tree node count calculator so learners can check depth and breadth for arbitrary a, b, and n without drawing hundreds of nodes by hand. Exam generators need a deterministic oracle that marks wrong a claimed leaf count or level count instead of accepting hand-wavy asymptotic guesses. Interview-prep tools and complexity visualisers pair the per-level arrays with charts so candidates see why balanced divide-and-conquer often spends the same work on every level when a equals b.
Engineering notebooks that prototype multiway splitters or parallel task graphs can sanity-check fan-out before writing production schedulers. Failed validation does not consume balance.
What you can do with it
Algorithms homework and tutoring
Let students submit a, b, and n for T(n)=a T(n/b)+f(n) and verify level count, leaf nodes, and the geometric node sequence against textbook drawings.
Exam and LMS auto-grading
Mark recursion-tree items with a deterministic oracle for total nodes and height instead of accepting asymptotic hand-waves as exact answers.
FAQ
How many nodes does the recursion tree of merge sort have?
For an input of 16 split into two halves at every step, there are 5 levels holding 1, 2, 4, 8 and 16 nodes. That makes 31 nodes in total, 16 leaves and 15 internal nodes.
When does the tree stop growing?
At the first level where the subproblem size drops to 1 or less. That level holds the base cases. The height is the number of levels minus one, so 5 levels mean a height of 4.
What do the two work distributions show?
One assumes every node costs the same, so most of the work sits in the leaves. The other assumes work grows with subproblem size, as in merge sort, where each of the 5 levels does an equal fifth of the work.
What if each step of the recursion creates only one subproblem?
Then the tree is a single chain, as long as the number of divisions needed to bring the size down to 1. The shrink ratio must always be greater than one, otherwise the subproblems would never get smaller.
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/recursion-tree-nodes \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"branching_factor":2,"shrink_ratio":2,"input_size":16}'const res = await fetch("https://api.kit.forhosting.com/dev/recursion-tree-nodes", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"branching_factor": 2,
"shrink_ratio": 2,
"input_size": 16
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/dev/recursion-tree-nodes",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"branching_factor": 2,
"shrink_ratio": 2,
"input_size": 16
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/dev/recursion-tree-nodes", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"branching_factor":2,"shrink_ratio":2,"input_size":16}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"branching_factor":2,"shrink_ratio":2,"input_size":16}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/dev/recursion-tree-nodes", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Example request
{
"branching_factor": 2,
"shrink_ratio": 2,
"input_size": 16
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "dev.recursion_tree_nodes",
"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.
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
What a recursion tree counts and how levels are defined
For branching factor greater than one the closed form for total nodes over L levels is a to the L minus one, all over a minus one, which this endpoint recomputes by summing the geometric series so fractional sizes and early base cases stay consistent with the walk.
Input contract, response fields, and work-share views
The recurrence string restates T of n in terms of a and b, and the formula field summarises the level rule and the closed total-node form. Pathological combinations that would exceed a safe level or node ceiling are rejected with a clear message so clients never hang on an exploding tree. Example: branching factor two, shrink ratio two, input size sixteen yields five levels with node counts one, two, four, eight, sixteen, total thirty-one nodes, and sixteen leaves—the classic perfect binary recursion tree for merge sort on a power-of-two array. POST a JSON body with three required finite numbers: branching_factor, an integer greater than or equal to one; shrink_ratio, a finite number strictly greater than one so subproblems shrink; and input_size, a finite number at least one for the root. Numeric strings are accepted; missing fields, non-finite values, non-integer or sub-one branching factors, shrink ratios not greater than one, and root sizes below one all fail with invalid_input and are not billed. On success the body echoes the three inputs and reports level_count, tree_height, total_nodes, leaf_nodes, and internal_nodes. The array nodes_per_level lists how many nodes sit at each level from the root downward. The array subproblem_size_per_level lists the size shared by every node on that level, rounded to twelve decimal places for stable cross-runtime equality. Two parallel fraction arrays sum to one: node_fraction_per_level divides each level node count by the grand total, modelling unit work per recursive call; size_work_fraction_per_level weights each level by nodes times subproblem size, modelling non-recursive work proportional to input size at that node.
Integration use cases
Complexity visualisers and interview prep
Feed nodes_per_level and size_work_fraction_per_level into charts so candidates see how work spreads across levels for merge-sort-style trees.
Technical questions
How do I count nodes in a divide-and-conquer recursion tree?
Send integer branching_factor a ≥ 1, shrink_ratio b > 1, and input_size n ≥ 1. The API walks levels with a^i nodes of size n/b^i until size ≤ 1 and returns totals plus per-level arrays.
What is the difference between level_count and tree_height?
level_count is the number of levels including the root (at least 1). tree_height is level_count minus 1, the number of edges on a path from the root to a leaf.
How is work distribution computed?
node_fraction_per_level is each level's node count over total_nodes. size_work_fraction_per_level weights each level by nodes times subproblem size, matching Θ(size) non-recursive work per call.
When does the calculator reject input?
Missing or non-finite fields, non-integer or sub-one branching_factor, shrink_ratio ≤ 1, input_size < 1, or trees that exceed the safe level/node ceiling fail with invalid_input and are not billed.
What does the recursion tree node count calculator cost?
The browser tool is free. API requests use prepaid KIT balance at $0.002 per successful call; invalid input is not billed.