Multiple AVL Trees From Sorted List?

Question

I'm working on an AVL tree assignment and I have a quick question about their definition - we're given a sorted list, and we have to generate an AVL tree from it in O(n) time. I've completed this (thanks to other help from StackOverflow!), but my result, while a valid AVL tree, is different from the result of the example provided. Are multiple AVL trees able to be generated from the same sorted list?

Thanks!

Answer 1

Yes. Consider the degenerate case of a tree with only two nodes. In this case, either node can be the root, and the other will be a leaf. The two are equivalent as far as overall balance goes.

Answer 2

Yes, for instance, these are two possible AVL trees for <1,2,3,4,5>:

(2 1 (3 4 5))

and

(4 (2 1 3) 5)

where (a T1 T2) denotes a tree with root a, left tree T1 and left right T2.