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:
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?