For a binary tree with n nodes, what are the minimum and maximum possible heights?

## The capacity argument Start from a single fact and everything else falls out: **level d of a binary tree holds at most 2^d nodes**, because each node on the level above contributes at most two children. Level 0 (the root alone) holds at most 1, level 1 at most 2, level 2 at most 4. Sum the levels of a tree of height h and you get the maximum node count: 1 + 2 + 4 + ... + 2^h = 2^(h+1) - 1 That total is achieved exactly when every level is full — a perfect tree, which therefore has 2^(h+1) - 1 nodes and 2^h leaves. Turn the inequality around. If n nodes must fit into h + 1 levels, then n <= 2^(h+1) - 1, which rearranges to h >= log2(n + 1) - 1. The smallest integer height that can hold n nodes is `floor(log2 n)` under edge counting, and a complete tree — every level filled before the next begins — attains it for every n. That is the **minimum**. The **maximum** needs no arithmetic. Give every node exactly one child and the tree is a chain: n nodes, n - 1 edges on the single root-to-leaf path, height n - 1. Nothing in the definition of a binary tree forbids this. "Binary" caps the number of children at two; it never requires that two be used. So for n = 1,000,000 the height lies somewhere in [19, 999,999]. That spread is the whole reason balanced structures exist. ## Working the bound in the direction interviews use The interesting property of `2^h` is how fast it moves. Each extra level roughly doubles capacity, so the level count barely responds to the data size: | nodes | minimum height (edges) | levels | |---|---|---| | 1,000 | 9 | 10 | | 1,000,000 | 19 | 20 | | 1,000,000,000 | 29 | 30 | Check the last row by hand, because this is the sort of arithmetic an interviewer asks you to do out loud: 2^29 = 536,870,912 and 2^30 = 1,073,741,824. A billion sits between them, so a complete tree over a billion nodes has height 29, meaning 30 levels from root to deepest leaf. If each level of a descent were a separate round trip somewhere, that is thirty of them — and it would still be thirty at two billion, and only twenty at a million. Capacity planning against a doubling bound is stubbornly flat, which is precisely why logarithmic structures scale so gracefully. The same arithmetic runs backwards for anything shaped like a single-elimination bracket. Draw the bracket as a tree whose leaves are competitors and whose internal nodes are the pairings that produce a winner: 256 competitors means 2^8 leaves, so the structure has height 8 and takes 8 rounds to resolve. Because such a bracket is full — every pairing has exactly two inputs — its internal node count is always one less than its leaf count: 255 pairings for 256 entrants. Doubling the field to 512 adds exactly one round, not twice the work per entrant. That is the `2^h` bound read as "how many halvings until one remains", which is the same bound that makes a balanced search cost log2 n steps. ## The claim to state carefully The most common wrong answer in this area is "a binary tree with n nodes has height log2 n". Three corrections make it right: 1. It is a **lower bound**, not an identity. log2 n is the best case; the actual height can be anything up to n - 1. 2. It requires a **shape guarantee** — completeness, or a balance condition enforced on every write. Insert sorted data into an unbalanced search structure and you get exactly the n - 1 chain. 3. It is **floor(log2 n)** under edge counting and one more than that under node counting. Say which you mean before quoting a number. And note the direction of the bound in the other sense too: knowing that a tree has height 29 tells you at most 2^30 - 1 nodes fit, but says nothing about how many are actually there. A height-29 tree may hold half a billion nodes or thirty. ## Why the range matters operationally Almost every tree operation costs O(h) — a walk from the root down one path. That single fact is why h, not n, is the number that appears in the complexity of search, insert and delete on tree structures, and why the entire engineering effort around trees goes into holding h near its lower bound. If you can state the range [floor(log2 n), n - 1] and name what pins h to the left end, you have the reasoning that every later tree topic builds on.