AVL Trees Possible


#1

What is the total number of possible AVL tree using 3 nodes (all three inclusive) for both labelled and unlabelled case?


#2

AVL trees are height balanced binary trees (Not to be confused with Binary Search Trees).
We generally apply the concept of AVL trees with BST to yield better optimization but in actual AVL trees are just height balanced trees.

Now coming to the above question,
For unlabelled case the answer is simply 1.

  o
 / \
o   o

This is the only possible tree in unlabelled case.

For labelled case there are totally 6 possible AVL trees possible.

  1                        1
 / \                      / \
2   3                    3   2  
              
  2                        2
 / \                      / \
1   3                    3   1  

  3                        3
 / \                      / \
1   2                    2   1