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.
   
2. If $\bf(v)=+1$, return Height($v.\text{left}$).
   
3. If $\bf(v)=0$, return Height($v.\text{right}$).
   
4. If $\bf(v)=-1$, 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.

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.
   
2. If $\bf(v)=+1$, return Height($v.\text{left}$).
   
3. If $\bf(v)=-1$, return Height($v.\text{right}$).
   
4. 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.

I am searching effective way to find out height of AVL tree. In each node there is balance factor ($bf$). $$bf(root)=height(root.left) - height(root.right). $$
And now we can find height in $O(\log n)$ time in a following recursive way:

when bf = 0 choose left or right subtree. when bf = 1 choose left subtree. when bf = -1 choose right subtree. 

The question is: If there exists more effective way ?

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.
   
2. If $\bf(v)=+1$, return Height($v.\text{left}$).
   
3. If $\bf(v)=0$, return Height($v.\text{right}$).
   
4. If $\bf(v)=-1$, 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.