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)
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}$$