Trees Revisited

We complete the trees sections in this post adding some more questions to the already posted ones.

1)What are splay trees?How are they different from normal trees?

2)What are the key operations which characterize splay trees?

3)How are AVL rotations different from the operations performed in splay trees?

4)Show that if all the nodes in a splay tree are accessed sequentially,then the total access time is O(N),regardless of the initial tree?

5)Given 2 binary trees T1 and T2 with same set of nodes,show how you can transform one in to the other?

6)Give an algorithm to transform a binary tree T1 into another binary tree T2?

7)Give an algorithm to find all the elements between 2 keys K1 and K2 with K1<=K2
in a binary search tree T?

8)How do you convert the parent-child tree to a child-sibling tree(assume the tree is a binary tree)?

9)Two binary trees T1 and T2 are isomorphic if T1 can be transformed into T2 swapping left and right children of the nodes in T1.Give an algorithm to report whether 2 given binary trees are isomorphic.

10)Analyze the complexity of the above algorithm and report whether there exists a linear solution to it?