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?


1 Answer 1


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.

  • Good point, it makes sense now. Thanks for your clear explanation!
    – rrazd
    Commented Feb 26, 2012 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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