0

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?

Improve this question
0

1 Answer 1

Reset to default
5

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.

Improve this answer
1
  • Good point, it makes sense now. Thanks for your clear explanation! Commented Feb 26, 2012 at 19:10

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.