Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question

migrated from stackoverflow.com 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
add comment

3 Answers 3

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
add comment

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
add comment

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
add comment

Your Answer

 
discard

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