6
$\begingroup$

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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
6
$\begingroup$

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$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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! $\endgroup$ Commented May 26, 2014 at 3:40
  • $\begingroup$ You're welcome. Just keep "recursive" in mind. $\endgroup$ Commented May 26, 2014 at 3:44
  • $\begingroup$ 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 $\endgroup$ Commented Sep 10, 2015 at 12:30
  • 1
    $\begingroup$ @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)$). $\endgroup$ Commented Sep 10, 2015 at 16:44

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.