Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Take the following tree:


Which node will be balanced first? 50 or 30

Case 1: 50
The tree is

          20    40
       10          50

Case 2: 30
The tree is

            /   \
          20     50
       10    30 

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

share|improve this question

migrated from Nov 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.

share|improve this answer
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.

share|improve this answer

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

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.