0
$\begingroup$

Given an AVL tree,what are the possible inputs so that the same given tree is formed(please dont mention brute force technique)?

$\endgroup$
  • $\begingroup$ Use BFS over the AVL tree to from some possible inputs. Each level can be permuted. This input doesn't require balancing. $\endgroup$ – kelalaka Oct 18 '18 at 11:51
0
$\begingroup$

AVL trees are binary search trees with additional balancing restrictions. For any binary search tree the root is the first node that should be in the input. After the root all smaller items go left, and all larger items go right. As long as we do not change the relative order of the items that go left, we obtain the same left subtree, and similarly for the right subtree. We can however swap to consecutive input items if they do not belong to the same subtree.

We can find any input sequence using this observation recursively. The following non-deterministic algorithm would work, its datastucture is a list of trees (subtrees of the original tree).

Start with the original tree. While any trees left, choose one of the trees, remove its root, and replace the original tree by its subtrees.

The order in which the nodes are removed is a possible input sequence. Extra details: The algorithm is related to the algorithm for finding a linear order matching a given partial order: topological sorting. The order is not the order that defines the AVL tree, instead it is the tree order itself.

$\endgroup$
  • $\begingroup$ can u give me the code(possibly in c++ pls)? $\endgroup$ – Sai Teja Oct 18 '18 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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