Compute height of AVL tree as efficiently as possible

Given an AVL tree, I want to compute its height as efficiently as possible. $\newcommand{\bf}{\text{bf}}\newcommand{\height}{\text{height}}$

Each node of an AVL tree stores its balance factor ($\bf$), defined as

$$\bf(v)=\height(v.\text{left}) - \height(v.\text{right}).$$

We can recursively compute the height of an AVL tree in $O(\log n)$ time, using the following recursive procedure:

Height($v$):

1. If $v$ is a leaf node, return 0.

1. If $\bf(v)=+1$, return Height($v.\text{left}$).

1. If $\bf(v)=-1$, return Height($v.\text{right}$).

1. If $\bf(v)=0$, return Height($v.\text{left}$). (returning Height($v.\text{right}$) would work too)

This recursive algorithm works, because the balance factor tells us which is taller, the left subtree or the right subtree, and the algorithm always recurses into the taller subtree.

My question is: Is there a faster algorithm? Can we do better than $O(\log n)$ time? Assume we can't augment the tree to store extra information in it; we are restricted to only the information that is already normally stored in an AVL tree.

No. There's a $\Omega(\lg n)$ lower bound. You can't do better than $O(\lg n)$ time. In fact, any algorithm has to visit at least $H-1$ nodes, where $H$ is the height of the tree.

Let $T_1$ be a tree of height $H$, where the balance factor at every node at all but the bottom two levels is 0. In other words, it is a perfect binary tree of height $H$, except that some subset of the leaves are missing; at the level above the leaves, all nodes have balance factor $+1$, $0$, or $-1$; and at all levels above that, the balance factor is $0$.

Let $T_2$ be an analogous tree of height $H+1$, i.e., it has height $H+1$ and the balance factor at all but the bottom two levels is 0.

Both $T_1$ and $T_2$ are AVL trees.

Now note that any algorithm has to visit at least $H-1$ nodes to distinguish $T_1$ from $T_2$. Their first $H-2$ levels look identical (every node has two children and has balance factor 0), so you can't tell them apart until you have visited at least $H-1$ nodes. To count as a correct algorithm for this problem, the algorithm has to produce the right answer on both $T_1$ and on $T_2$.

Consequently, any algorithm has to have worst-case running time at least $H-1$, i.e., $\Omega(H)$.

StackExchange Computer Science Q#50486, answer score: 4