Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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|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

 
discard

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.