Sign up ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

This question already has an answer here:

Question: If an AVL tree has height h (assume h ≥ 2), what is the maximum possible difference between the number of nodes in its two subtrees? Prove your answer. Your answer should not use big-Oh or big-Theta.

I drew six trees and drew the max number of nodes I could on one tree and the min number of nodes on the other subtree while keeping it an AVL tree. Here is table with the information for number of minimum nodes in left subtree, max number of nodes in right subtree and difference between the number of nodes between the two trees:

But I simply cannot figure out a pattern for the maximum possible difference between the number of nodes in the two subtrees. My current guess is that the max possible difference between the two number of nodes is 2h-1 - (h-2).

Here is a picture of the diagrams I drew to come up with the numbers in the table above:

I drew as little nodes as possible on the left subtree and drew as many nodes as I could on the right subtree.

share|cite|improve this question

marked as duplicate by Raphael May 26 '14 at 10:21

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer 1

up vote 2 down vote accepted

I assume that we start labeling heights from $0$.

Actually your approach is right. You must consider the left-side (or right-side) sub-tree with the least possible amount of nodes and the right-side (or left-side) sub-tree with the most possible amount of nodes, and both sub-trees must be AVL trees too. For this purpose, we fix the height of left-side sub-tree to $h-2$ (doing so, the bottommost node of this sub-tree would be at height $h-1$ of the main tree) and we fix the height of right-side sub-tree to $h-1$. Now, we should answer following questions:

  1. What is the minimum number of nodes in an AVL tree of height $h-2$?
  2. What is the maximum number of nodes in an AVL tree of height $h-1$?

Answer to question 1: By recursions and assuming that $n(h)$ is the minimum number of nodes of an AVL tree of height $h$ we can easily get: $$ \begin{array}{rl} n(h) &=& n(h-1)+n(h-2)+1\\ n(1)&=&2\\ n(0)&=&1 \end{array} $$

Answer to question 2: In this case, we're dealing with a perfect tree (which is an AVL tree too) and we must find the number of nodes in a perfect tree of height $h-1$.

So, the answer to your question would be: $$ 2^h - 1 - n(h-2) $$

As an example, if $h=2$, this formula returns $2$, which is not the value you have got, and I think that's because you start labeling heights from $1$.

share|cite|improve this answer
That was beautiful. How the heck did you come up with the idea of the recursive function? It was so simple now you showed me how you did it. Spent hours on this question and couldn't do it. Thanks! –  user2635911 May 26 '14 at 3:40
You're welcome. Just keep "recursive" in mind. –  Mowji May 26 '14 at 3:44
I don't understand how to resolve the recursion n(h) from the answer. If it din't have +1, it would be the formula for the n-th Fibonacci number –  Maksim Dmitriev Sep 10 at 12:30
@MaksimDmitriev It's better to make this recursive equation, linear homogeneous with constant coefficients (read about it: link). We must make that "+ 1" disappear. We can do this by simplifying $n(h) - n(h-1) = (n(h-1) + n(h-2) + 1) - (n(h-2) + n(h-3) + 1)$. This lead to $n(h) = 2n(h-1) - n(h-3)$. Then you can read Wikipedia article mentioned above to solve it. Note that for this new recursive equation you need 3 initial conditions ($n(0), n(1)$ and $n(2)$). –  Mowji Sep 10 at 16:44

Not the answer you're looking for? Browse other questions tagged or ask your own question.