CODEWITHSUNDEEP
algorithmdata-structuresbinary-search-tree
user496934
user496934

Reputation: 4020

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

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.

Upvotes: 4

Views: 8218

Answers (5)

roshan jha
roshan jha

Reputation: 11

Node buildTree(int inorder[], int start, int end) 
    {
        if(start>end)return null;
      int mid=start+(end-start)/2;
      Node rroo=new Node(inorder[mid]);
      rroo.left=buildTree(inorder,start,mid-1);
        rroo.right=buildTree(inorder,mid+1,end);
      return rroo;
    }

Upvotes: 1

Hariom Patidar
Hariom Patidar

Reputation: 1

yes it can be constructed but the bst constructed will always be right skewed tree as inorder of bst always in sorted order

Upvotes: -1

Sonu Kumar Keshri
Sonu Kumar Keshri

Reputation: 11

TreeNode* solve(vector<int>& v, int l, int r){
  if(l>r){
    return NULL;
  }
  int m = (l+r)/2;
  TreeNode* root = new TreeNode(v[m]);
  root->left = solve(v, l, m-1);
  root-> right = solve(v, m+1,r);
  return root;
}

TreeNode *constructFromInOrder(vector<int> &inorder)
{
  return solve(inorder, 0, inorder.size()-1);
}

c++ code to convert Inorder to BST

Upvotes: 1

trincot
trincot

Reputation: 350137

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.

Upvotes: 5

shine
shine

Reputation: 97

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/

Upvotes: 9

Related Questions