AVL tree height in O(logn)

Question

I'm trying to figure out a way to calculate the height of the tree using the fact that each nodes knows about its balance. This complexity must be in O(logn)

Here's what I've got so far.

if(!node)
  return 0
if(node.balance > 0)
  return height(node.right) + 1
if(node.balance < 0)
  return height(node.left) + 1
return max( height(T.left), height(T.right)) + 1

My thought was that if the tree is right heavy, traverse the right side and ignore the left. If the tree is left heavy, ignore the right and keep traversing in there. However, I'm a little confused as to what to do if the tree is balanced. At that point, wouldn't we be forced to run max( height(T.left), height(T.right)) + 1 which would mean that each node in the subtree would be visited, hence making this complexity O(n) either way?

user268396 user268396 · Accepted Answer · 2015-11-15T01:39:27

The height/depth is linked to the size of the tree as a direct result of the tree being balanced. Because an AVL is balanced, you can use its structure to calculate the depth of the tree in O(1) if you know its size:

   lg N = log(N) / log(2) -- define a helper function for 2-log
   depth N = 1 + floor(lg(N)) -- calculate depth for size N > 0.

Picture the tree as it fills: each new 'level' of depth corresponds to a threshold in the size of the tree being reached, namely the next power of 2.

You can see why this is: the deepest row of the tree is 'maxed out' when the size of the tree N is just one short of a power of two. The 1+ corresponds to that deepest row which is currently being filled until the depth of the tree changes to the next 'level', the floor(lg(N)) corresponds to the depth which the tree had on the previous 'level'.

AVL tree height in O(logn)

1 Answers