Finding Height of a node in an AVL Tree for Balance Factor calculation
By this definition, height of leaf is 0.
This is correct.
BUT if height is starting with zero, I can have the following AVL trees too, right?
No, the parent of the leaf has height 1, as the path from that node to the leaf has 1 edge.
So it should be:
O -- height 2, balance factor 2
/
O -- height 1, balance factor 1
/
O -- height 0
The balance factor of the root is 2 because the height of its left subtree is 1 and that of its right subtree is -1 (!). Note that if a single node has height 0, then an empty tree has height -1. This is also what is mentioned in Wikipedia:
The height of a node is the length of the longest downward path to a leaf from that node. [...] The root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has height −1.
And so these are not valid AVL trees: they need to be rebalanced.