I have a tree as

enter image description here

Is it an AVL tree? it seems to balanced for me.


closed as unclear what you're asking by Evil, David Richerby, dkaeae, Gilles 'SO- stop being evil' Jul 29 at 16:01

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.


No, it is not an AVL tree.

A binary tree is defined to be an AVL tree if $${\text{BalanceFactor}}(N)\in {\{-1,0,1\}} $$ holds for every node $N$ in the tree, where $$\text{BalanceFactor}(N):=\text{Height(RightSubtree(N))} - \text{Height(LeftSubtree(N))}$$

Consider Node 2. Its left subtree is a degenerated tree of height 2. Its right subtree is empty. Whether the height of an empty tree is 0 or -1 is up to debate. In the context of AVL trees, I would prefer to define the height of an empty tree to be -1. $$\text{BalanceFactor}(\text{Node 2}) = (-1) - 2 = -3\not\in\{-1,0,1\}.$$ So the tree in the question is not balanced, although we can say it is balanced at the root.

In fact, every kind of definition of a balanced (rooted) tree (that I know) requires all of its subtrees be balanced of the same kind. So, the tree in the question is unlikely to be considered balanced for any definition of a balanced tree. For example, it is not a $1/2$-weight balanced tree.

In summary, the subtree whose root is node 2 does not look balanced, which makes the tree not balanced.


Not the answer you're looking for? Browse other questions tagged or ask your own question.