# AVL Tree Balancing Problem

Take the following tree:

50
40
30
20
10

Which node will be balanced first? 50 or 30

Case 1: 50
The tree is

30
20    40
10          50

Case 2: 30
The tree is

40
/   \
20     50
10    30

Well, both are AVL Trees, so are both correct?

-

## migrated from stackoverflow.comNov 9 '11 at 20:00

This question came from our site for professional and enthusiast programmers.

If you ask me I'd do 30 first, but what about 50? – nbaztec Jan 6 '11 at 16:33

Your first tree is not an AVL tree. Even minus an element it is not an AVL tree (so we can't even consider it as an AVL tree undergoing balance).

AVL operations are defined on AVL trees to produce a new AVL tree. They are defined in terms of the node that was inserted or deleted.

So, we don't have an AVL tree to start, and we have no information about how we got that tree (was something just inserted or deleted, and if so, what?). In short, I think the question needs to be clarified.

-
That was exactly what I thought. Saw this in a book (Case 1). Talk about bad authors :) – nbaztec Jan 8 '11 at 5:19
if the OP provides an insertion order then we'll know what the tree will look like. – Kevin Nov 9 '11 at 20:05
Exactly the tree to begin with is left heavy - which it would never have been if it were balanced as nodes were added to it. How can you "balance" something which has the operation undefined on it? – yati sagade Nov 9 '11 at 20:45

It is easier to think about the problem recursively by balancing 30 prior to 50. Since leaf nodes (with no child nodes) are already balanced, you can balance the tree in a bottom up fashion knowing that all nodes below the current node are balanced trees.

-

z5h is right. If you want an AVL tree you have to build it, adding the elements one by one and balancing if necessary.

-