Finding Height of a node in an AVL Tree for Balance Factor calculation

Question

AVL tree is a binary search tree that is balanced i.e height = O(log(n)). This is achieved by making sure every node follows the AVL tree property:

Height of the left subtree(LST) - Height of the right subtree(RST) is in the range [-1, 0, 1]

where Height(LST) - Height(RST) is called Balance factor(BF) for a given node.

The height of the node is usually defined as, "length of the path(#edges) from that node to the deepest node" eg:

By this definition, height of leaf is 0. But almost everytime while discussing AVL trees, people consider height of the leaf to be 1.

My question is, can we take the height of leaf to be 0? This will make following BSTs also AVL trees, right?

Height concept confuses me because of these articles:

• https://www.geeksforgeeks.org/minimum-number-of-nodes-in-an-avl-tree-with-given-height/
• https://www.tutorialspoint.com/minimum-number-of-nodes-in-an-avl-tree-with-given-height-using-cplusplus

Firstly, they start the height with 0. Then they say, minimum number of nodes required for avl tree of height 2 to be 4 BUT if height is starting with zero, I can have the following AVL trees too, right?

Answer 1

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.