Assuming that you do not make any turns (etc.) to balance the tree, you can get a response from the structure of the tree: new nodes are always added as descendants of existing nodes, so any node above the tree should precede its descendants, but may be rebuilt at will with their "peers" (nothing that neither his parent nor a descendant).
For example, since you have C as the root of the tree, C should be the first element that has been read from the stream. Since its descendants are B and P , the next entry element should have been one of these two. B has no descendants, but P has two: H and Z , so they had to be read after P , but could be in any order relative to B Similarly, Z can be in any order with respect to H and D , but H must precede D
Change As for generating all of these permutations, one simple (trick) way would be to use Prolog. Basically, you encode these dependencies as “facts”, and it will generate all permutations that correspond to these facts. In fact (no pun intended), this is pretty much a description of what Prolog does / does.
By doing this yourself, you probably want to do most of the work recursively. Correct ordering is the root, followed by any alternation of the permissible orders of its descendants.
Regarding how to do the rotation, you would (for example) generate one valid order of the left subtree and one valid order of the right subtree. Combine them into an array with all the elements from the left subtree at the beginning and all those from the right subtree at the end. For demonstration, suppose the tree also contains A (as a descendant of B , which you show). In the array, our data from our subtrees is as follows:
BAPHZD
Then we start with the last element from the left subtree and “walk” through each array to the right, each time creating a new permutation:
BPAHZD PBAHZD BPHAZD PBHAZD PHBAZD [ ... ]
For each valid order of the left subtree, you need to do all these alternations with each valid order of the right subtree (and return it to the parent, which will do the same).