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.

Given a binary search tree, I understand why I can use breadth-first and pre-order traversal to list the entries of the tree in such a way as to reconstruct the tree in the order in which its traversed.

However if we now consider an AVL tree and we want to traverse the tree in such a way as to recreate the same AVL tree (similar as to what we did with the plain binary tree) then why does breadth first traversal always work and why does pre-order not work with this case given that it works for standard binary trees?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

Unlike a plain binary tree, AVL trees are self-balancing. When an element is inserted into an AVL tree, the tree may need to perform node rotations in order to maintain a certain tree depth, which allows for logarithmic lookup time. So, if you try to build a second AVL tree using pre-order node traversal on an existing AVL tree, the resulting tree will not necessarily have the same node structure, because it may need to perform node rotations in order to keep the tree balanced.

share|improve this answer
    
Good point, it makes sense now. Thanks for your clear explanation! –  rrazd Feb 26 '12 at 19:10

Your Answer

 
discard

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

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