Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If we have a quad tree where each node must have 0 or 4 children, is there an expression that can me the maximum height of a quad tree with $n$ nodes?

share|cite|improve this question
up vote 3 down vote accepted

A tree of height $m$ where at each level only one node has children will have $1+4(m-1)$ nodes, assuming a tree with only one node has height one. The height will be $m=\frac{n+3}{4}$ for $n$ nodes. If your number of nodes is not $1 \pmod 4$, it won't work as each branch adds 4 nodes.

share|cite|improve this answer
I think you've used $n$ for both the height and the number of nodes. – joriki Apr 6 '11 at 19:25
@joriki: You are right. Fixed. Thanks. – Ross Millikan Apr 6 '11 at 19:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.