Topics

# BST Sequences

Hard
0/120
Average time to solve is 50m
Contributed by
1 upvote

## Problem statement

You are given a binary search tree consisting of distinct elements. The binary search tree is created by traversing through the sequence from left to right and inserting each element. You need to print all the sequences or ways that would result in creating the given BST.

Note:
``````Keep in mind that while merging the sequences the relative order of elements should be preserved.
``````
For example :
``````For the given binary search tree
``````

``````The valid BST sequences for the above BST are:
4 2 1 3 5 6
4 2 1 5 3 6
4 2 1 5 6 3
4 2 3 1 5 6
4 2 3 5 1 6
4 2 3 5 6 1
4 2 5 1 3 6
4 2 5 1 6 3
4 2 5 3 1 6
4 2 5 3 6 1
4 2 5 6 1 3
4 2 5 6 3 1
4 5 2 1 3 6
4 5 2 1 6 3
4 5 2 3 1 6
4 5 2 3 6 1
4 5 2 6 1 3
4 5 2 6 3 1
4 5 6 2 1 3
4 5 6 2 3 1

You need to print all of them.
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
``````1 <= T <= 10
0 <= N <= 10
1 <= data <= 10^4

Time Limit: 1sec
``````
Sample Input 1:
``````1
4 2 5 1 3 -1 6 -1 -1 -1 -1 -1 -1
``````
Sample Output 1:
``````4 2 1 3 5 6
4 2 1 5 3 6
4 2 1 5 6 3
4 2 3 1 5 6
4 2 3 5 1 6
4 2 3 5 6 1
4 2 5 1 3 6
4 2 5 1 6 3
4 2 5 3 1 6
4 2 5 3 6 1
4 2 5 6 1 3
4 2 5 6 3 1
4 5 2 1 3 6
4 5 2 1 6 3
4 5 2 3 1 6
4 5 2 3 6 1
4 5 2 6 1 3
4 5 2 6 3 1
4 5 6 2 1 3
4 5 6 2 3 1
``````
Explanation For Sample Input 1:
``````The binary search tree will look like this:
``````

``````In the above Binary Search Tree, all the valid sequences are:

4 2 1 3 5 6
4 2 1 5 3 6
4 2 1 5 6 3
4 2 5 1 3 6
4 2 5 1 6 3
4 2 5 6 1 3
4 5 2 1 3 6
4 5 2 1 6 3
4 5 2 6 1 3
4 5 6 2 1 3
4 2 3 1 5 6
4 2 3 5 1 6
4 2 3 5 6 1
4 2 5 3 1 6
4 2 5 3 6 1
4 2 5 6 3 1
4 5 2 3 1 6
4 5 2 3 6 1
4 5 2 6 3 1
4 5 6 2 3 1
``````
Sample Input 2:
``````2
2 1 3 -1 -1 -1 -1
7 -1 -1
``````
Sample Output 2:
``````2 1 3
2 3 1
7
``````
Console