Can we construct BST from inorder sequence?

Question

We can construct a Binary Search Tree (BST) from a preOrder or postOrder sequence. But can we construct a BST from an inorder sequence alone? I think it is not possible to construct a BST using an inOrder sequence, as we cannot find its root element.

Answer 1

You are correct. Two different Binary Search Trees can have the same inorder sequence, so you wouldn't know which one to pick. If however, it would be OK to pick any BST that has that inorder sequence, then it is possible.

But I guess your question is about reconstructing the same BST as the tree from which the inorder sequence was derived. That is not possible: by converting a BST to an inorder sequence, you lose information. Even if you would be given the root as additional information, you would not generally be able to do it. In fact, the shape of the BST can be anything possible with the given number of nodes.

The smallest example is inorder [1, 2]. It can represent both of these trees:

           2           1
          /             \
         1               2

If in this case you were given the root as extra information, then it would of course be possible to derive the BST from it.

The next smallest example: [1, 2, 3]. These trees all have that as inorder sequence:

          3           2            1
         /           / \            \
        2           1   3            2
       /                              \
      1                                3

Also here it is true that if you were given the root as extra information, you would be able to know which of the three BSTs was the right one.

But once we get to larger trees, we would not always be able to know the right BST, even if we were given the root.

Note also that a BST does not have to be optimally balanced. But even if we would only consider optimally balanced BSTs, an inorder sequence does not uniquely define the tree. The example with 2 nodes above is already proof of that. But let's look at four nodes for which the inorder sequence would be [1, 2, 3, 4]. The most-balanced trees with that inorder sequence are:

        3             3            2          2
       / \           / \          / \        / \
      2   4         1   4        1   4      1   3
     /               \              /            \
    1                 2            3              4
        

And here we also see that if we were given the root of the optimally balanced BST, there still would be two possibilities left.