Algorithms – Why Can’t an AVL Tree Be Recreated Using Pre-Order Traversal?

algorithmsbinary treetrees

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?

Best Answer

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.

Related Solutions

Algorithms – In-Order Traversal of M-Way Trees

I believe the in order traversal of m-way trees can be generalized. Lets take the example of the tree you have provided. Following are the steps for that :

Go to the left most node first and print its first element. Then check if there is any subtree between this element and the next element in that node. If it exists then apply the same approach on that sub-tree, else print element. Similarly move through all the elements in that node. Since in your tree there is no sub-tree in your left most node so print all the elements. Thus the output of first step will be : 2, 5, 6.
Then apply same algo in the parent node and move up towards your root node recursively.

Thus the output of the in-order traversal of your tree should be :

2,5,6, 7, 9,12,17, 20, 26,31,39, 45, 46,53,71

You can refer to this ppt for more info : In order Traversal of M-Way Trees

Usefulness of pre and post order traversal of binary trees

You need to do various things with trees, like translate between the data structure and some serial representation, like on a file or in a language.

So, for example, suppose you have a parse tree like this:

    *
   / \
  +   \
 / \   \
A   B   C

You could serialize it as * + A B C by walking it in prefix order, or as A B + C * by walking it in postfix order. If you work at all with language processors, such things need to be second-nature.

Best Answer

Related Solutions

Algorithms – In-Order Traversal of M-Way Trees

Usefulness of pre and post order traversal of binary trees

Related Topic