Finding the height of a perfect quadtree

Question

I am sure this must be trivial but I can't find this specifically anywhere. I have a perfectly balanced, full quadtree. I know the total number of nodes in the tree. I want to find out the height without traversing the tree - what is the formula for this?

(Not homework)

Just to be sure, by a perfectly balanced, full quadtree, you mean that there are $4^n$ nodes at level $n$, and each internal node has exactly four children, correct? — saulspatz, Jul 22 '19 at 15:02

score 2 · Accepted Answer · answered Jul 22 '19 at 15:08

2

Suppose there are $N$ nodes and the height is $n$. Since there are $4^k$ nodes at level $k$, we have $$N=\sum_{k=0}^n4^k={4^{n+1}-1\over3}$$ This gives $$4^{n+1}=3N+1\implies\boxed{n=\log_4(3N+1)-1}$$

answered Jul 22 '19 at 15:08

saulspatz

53,131

Finding the height of a perfect quadtree

1 Answers1