This question already has an answer here:
- AVL trees are not weight-balanced? 1 answer
Question: If an AVL tree has height h (assume h ≥ 2), what is the maximum possible diﬀerence 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.