The answer to your question depends on whether you are allowed to have equal values in the BST, which may differ from each other. For example, if your BST stores key / value pairs, then it is not always possible to include one BST for these key / value pairs in another BST for the same key / value pairs.
The reason for this is that the node traversal in the BST remains unchanged no matter how many tree rotations are performed. As a result, it is not possible to convert from one BST to another, if the traversal of nodes in order comes out differently. Suppose you have a BST with two copies of number 1, each of which is annotated with a different value (for example, A or B). In this case, there is no way to turn these two trees into each other by turning the tree:
1:a 1:b \ \ 1:b 1:a
You can verify this by roughly forcing a (very small!) Set of possible trees that you can do with turns. However, it is enough to notice that traversing the first tree gives 1: a, 1: b, and traversing the second tree gives 1: b, 1: a. Therefore, there will not be enough rotations to convert between trees.
On the other hand, if all values are different, then you can always convert between two BSTs using the correct number of tree rotations. I will prove this using an inductive argument for the number of nodes.
As a simple base case, if there are no nodes in the tree, there is only one possible BST containing these nodes: an empty tree. Therefore, you can always convert between two trees with zero nodes in them, since the start and end tree should always be the same.
For the inductive step, suppose that for any two BSTs from 0, 1, 2, .., n nodes with the same values, you can always convert from one BST to another using rotations. We will prove that for any two BST made from the same n + 1 values, you can always convert the first tree to the second.
To do this, we start by making a key observation. With any node in BST, you can always apply tree rotation to pull that node to the root of the tree. To do this, we can apply this algorithm:
while (target node is not the root) { if (node is a left child) { apply a right rotation to the node and its parent; } else { apply a left rotation to the node and its parent; } }
The reason this works is because every time a node rotates with its parent, its height increases by one. As a result, after applying a sufficiently large number of revolutions of the above forms, we can get the root to the top of the tree.
Now this gives us a very simple recursive algorithm that we can use to change any BST to another BST using rotations. The idea is this. First, consider the root node of the second tree. Find this node in the first tree (it's pretty simple, since it's BST!), Then use the above algorithm to pull it to the root of the tree. At this point, we turned the first tree into a tree with the following properties:
- The first root of the node tree is the node root of the second tree.
- The first right subtree of the tree contains the same nodes as the second tree of the tree, but possibly with a different shape.
- The first left subtree of the tree contains the same nodes as the second tree on the left of the subtree, but possibly with a different shape.
Therefore, we could then recursively apply the same algorithm so that the left subtree has the same shape as the left subtree of the second tree, and to make the correct subtree, have the same shape as the right subtree of the second tree. Since these left and right subtrees must have strictly no more than n nodes each, according to our inductive hypothesis, we know that this can always be done, and therefore the algorithm will work as intended.
To summarize, the algorithm works as follows:
- If two trees are empty, we are done.
- Find the root node of the second tree in the first tree.
- Apply rotations to bring this node to the root.
- Recursively change the left subtree of the first tree to the same shape as the left subtree of the second tree.
- Recursively change the right subtree of the first tree to the same shape as the right subtree of the second tree.
To analyze the runtime of this algorithm, note that to complete steps 1 to 3, no more than O (h) steps are required, where h is the height of the first tree. Each node will be brought up to the root of some subtree exactly once, so we do this a total of O (n) times. Since the height of the n-node tree never exceeds O (n), this means that no more than O (n 2 ) is required to complete the algorithm. It is possible that it will be much better (for example, if two trees already have the same shape, then this is done in O (n) time), but this gives a good estimate of the worst case.
Hope this helps!