Dsa
Binary Search Tree
Hard
Find All Valid BST Sequences
Given a list of integers representing a unique BST's preorder traversal, write a program to find all the valid sequences of node insertions that could lead to the same BST. The results should be printed in lexicographical order.
Input Format:
- A single line containing space-separated integers representing the preorder traversal of the BST.
Output Format:
- Each valid sequence in a new line, sorted in lexicographical order.
Example:
Input:
2 1 3
Output:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Key concepts
binary_search_treebacktrackingvalid_sequences
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now