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

Yes it is possible to construct a binary search tree from an inorder traversal.

Observe that an inorder traversal of a binary search tree is always sorted.

There are many possible outcomes, but one can be particularly interested in producing a tree that is as balanced as possible, so to make searches in it efficient. One way to produce an inefficient binary search tree, is to keep adding new nodes to the right of the last inserted node. The resulting binary search tree is then skewed.

If for example the inorder traversal is 1,2,3,4,5,6, we would get this tree:

 1
  \
   2
    \
     3
      \
       4
        \
         5
          \
           6

That is not very helpful as binary search tree, as it really has degenerated into a single chain, and a search in that tree is no better than performing a search from left to right in the input array.

A much more efficient alternative would be this binary search tree, which has the same inorder traversal:

       3
      / \
     2   5
    /   / \
   1   4   6

Algorithm

The algorithm to produce a rather balanced binary search tree can indeed be a recursive one:

1. If the given array (traversal) is empty return null (emtpy tree)
2. Take the middle value of the given array (traversal) and create a node for it.
3. Take the subarray at the left of the selected array value, and perform the algorithm recursively for it. This returns a node (rooting a subtree), which should be attached as left child of the node created in step 2.
4. Take the subarray at the right of the selected array value, and perform the algorithm recursively for it. This returns a node (rooting a subtree), which should be attached as right child of the node created in step 2.
5. Return the node created in step 2.