Can a binary search tree be constructed from only the inorder traversal?

Question

Wanted to check if there is a way to construct a binary search tree from only the inorder traversal which will be in sorted order. I am thinking there might be some way we can do it recursively, but not able to figure it out. Any pointers would be appreciated.

Answer 1

A BST has exactly one in-order traversal, but more than one BST can be constructed with a given in-order traversal. Hence, Yes, it is possible to construct a BST with a given in-order traversal, but you may not end up with the same tree whose in-order traversal you've started with.

Check this article for more info: https://www.geeksforgeeks.org/find-all-possible-trees-with-given-inorder-traversal/