How to approach this problem?

I have analysed this problem and have attempted this problem but haven’t solved it yet. I need some deep insight how to tackle questions of this pattern and get the right intuition.
Till now what I have understood from the problem:-

  1. There are many sequences of data that may lead to same BST.
  2. In all sequences the root node must appear before it’s child so as to maintain relative order of nodes.
  3. We could do this problem recursively as we can see for each node it have two choices:
    i) start with left sequence
    ii) start with right sequence
  4. We can generate combinations of these sequences
    I am stuck in how to do these, how can I generate and validate my sequence
    Thanks in advance :’)

Hey thats brilliant thinking to have gone so far ahead. Let me help you out a little here. Suppose you have a BST as follows :

 
       2
      / \
     1   3

Then arranging wont be an issue since :

2 1 3
2 3 1

will be the only outcome.
However consider a tree :

 
       3
      / \
     1   5
    /   / \
  -1   4   7

You can have a lot of issues.
For the subtree rooted at 1, you can have only 1 -1 as an arrangement. For the subtree rooted at 5 you can have 5 4 7 and 5 7 4 as the 2 options.

So for the subtree rooted at 3 you need to merge the options for the left subtree and right subtree in such a manner that their relative order remains the same i.e .1 can never occur after -1 in the merged array . So the answers will be :

3 1 -1 5 4 7 
3 1 5 -1 4 7 
3 1 5 4 -1 7 
3 1 5 4 7 -1
3 5 1 -1 4 7 
... and so on

Does this help you think??

Yeah i got some insight let me re-attempt the problem and get back to you :’). Thanks for that.

Hey could you discuss about the precise time complexity of this problem according to the above approach ? :’)