Possible permutations of BST's input [closed]

Question

I am given a string, i.e. "CPHBDZ". By inserting (in this order) letters to a BST I will have:

  C
 / \
B   P
   / \
  H   Z
 /
D

If we change order of the string to "CBPHDZ" we will get identical tree. And I have to find and list all permutations of the input string that provide the same BST. I came up with how to calculate a number of those permutations but I can't figure out any algorithm which actually finds them.

Answer 1

Assuming you're not doing any rotations (etc.) to balance the tree, you can derive an answer from the structure of the tree: new nodes are always added as descendants of existing nodes, so any node higher in the tree must precede of its own descendants, but can be rearranged at will with its "peers" (anything that's neither its parent nor descendant).

For example, since you have C as the root of the tree, C must have been the first item that was read from the stream. Since its descendants are B and P, the next item in the input had to be one of those two. B doesn't have any descendants, but P has two: H and Z, so they had to be read after P, but can be in any order with respect to B. Likewise, Z can be in any order with respect to H and D, but H must precede D.

Edit: As to generating all those permutations, one simple (cheating) way would be to use Prolog. Basically, you encode that dependencies as "facts", and it'll generate all the permutations that fit those facts. In fact (no pun intended), this is pretty much a description of what Prolog is/does.

Doing it on your own, you'd probably want to do most of the job recursively. A valid ordering is a root followed by any interleaving of the valid orders of its descendants.

As far as how to do the interleaving, you would (for example) generate one valid order of the left sub-tree and one valid order of the right subtree. Put them together into an array with all the items from the left sub-tree at the beginning, and all those from the right sub-tree at the end. For demonstration, let's assume the tree also contained an A (as a descendant of the B you show). In an array, our data from our sub-trees would look like:

B A P H Z D

Then we start from the last item from the left sub-tree, and "walk" each across the array to the right, generating a new permutation each time:

B P A H Z D
P B A H Z D
B P H A Z D
P B H A Z D
P H B A Z D
[ ... ]    

For each valid order of the left sub-tree, you need to do all these interleavings with each valid order of the right sub-tree (and return it to the parent, which will do the same).

Answer 2

In Python,

tree = {
    'C' : ['B', 'P'],
    'P' : ['H','Z'],
    'H' : ['D']}

def f(tree,  ready):
    if not ready:
        return [[]]
    else:
        rv = []
        for r in ready:
            for rest in f(tree,
                          [n for n in ready if r != n] + tree.get(r, [])):
               rv.append([r] + rest)
        return rv

for o in f(tree, 'C'):
    print ''.join(o)