Is this problem has a smart solution?

#1

I am trying really hard to figure it out, the only solution I came with is to find all the unique permutations of [1,2,…,n], than iterate through them and and build trees. every time I build a tree I check if we saw him before - and if yes we throw him away, else we keep it.

This is extremely not efficient, and I didn’t thought it was the solution, so I tested the expected output with the number “6”. in the output I saw the two following permutations:
1,2,3,5,4,6
1,2,3,5,6,4
which generate the same tree if inserted from left to right.

so I am not sure anymore if there is any efficient solution… any hints?

#2

I don’t know if it’s smart to everyone, but here are the main features of the one that I used:

  • There is an algorithm to produce unique, =ordered= permutations iteratively (and in-place). Once you’ve got that you don’t need to maintain a table of ones already generated.
  • I treat each permutation as list of preorder-traversed node values. This made validating the tree as a proper BST easier (and fail faster) for my money.
#3

You can build it recursively and you don’t need to check the values seen so far because the trees have the binary search tree property.
You can split the current range [A…B] in [A…X-1] and [X+1…B] and generate recursively the trees with X as root.