top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Is it possible to construct BST by using Inorder Traversal?

+5 votes
1,163 views

I came to know that ,construction of BST is possible by using PreOrder and PostOrder traversal but is it possible to construct a BST using InOrder traversal , if not then why?

posted Jun 22, 2016 by Shahsikant Dwivedi

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button
Sir, I think given solution is not applicable for Binary Search Tree , as right child is not greater. Consider a scenario, if Preorder traversal is 5,3,2,4,8,7,9 we can easily figure out the root node which is 5 in this case and construct our Binary search tree accordingly , same goes in case of Postorder, for the given Preorder ,Postorder. traversal is 2,4,3,7,9,8,5 in this case last one is root which is again 5 , but if only Inorder traversal is given which is 2,3,4,5,7,8,9  how can I figure out the root node I can take 7 or 8 or 9 any of them as root as I am not sure which one is the root. Kindly correct me if I am wrong, thanks.
I missed the term search and above solution is for Binary tree, my bad.
Let me see if it is possible, give me some time.
Just a query,
Inorder traversal is the sorted array so now we can say the problem is reduced to construct a BST from the sorted array. Let me know your thoughts.

If agree with my thought process then u can use the following link
http://www.geeksforgeeks.org/sorted-array-to-balanced-bst/
yes, indeed the inorder traversal is sorted but there is still a confusion, according to the algorithm sorted array's middle element will be root and element to the left and elements to the right will be left and right subtree accordingly.
       8
      /  \
    5    12   
 /    \
4    6
/
3
sir, for the following tree preorder traversal is :- 8,5,4,3,6,12 , root is leftmost :8
Postorder traversal is :3,4,6,5,12,8 here the rightmost element is root, which is 8, but according to the algorithm in inorder traversal which is <3,4,5,6,8,12> . 6 will be chosen as root which was not the original root in tree ,thus will result an entirely different tree.
You will not get a unique tree for that you need two traversals,
above link was for the balanced tree...
thanks sir

1 Answer

–3 votes

Given Inorder Traversal of a Special Binary Tree in which key of every node is greater than keys in left and right children, construct the Binary Tree and return root.

Examples:

Input: inorder[] = {5, 10, 40, 30, 28}
Output: root of following tree

     40
   /   \
  10     30
 /         \
5          28 

Input: inorder[] = {1, 5, 10, 40, 30,
15, 28, 20}
Output: root of following tree

          40
        /   \
       10     30
      /         \
     5          28
    /          /  \
   1         15    20

The idea used in Construction of Tree from given Inorder and Preorder traversals can be used here. Let the given array is {1, 5, 10, 40, 30, 15, 28, 20}. The maximum element in given array must be root. The elements on left side of the maximum element are in left subtree and elements on right side are in right subtree.

         40
      /       \  
   {1,5,10}   {30,15,28,20}

We recursively follow above step for left and right subtrees, and finally get the following tree.

          40
        /   \
       10     30
      /         \
     5          28
    /          /  \
   1         15    20

Algorithm: buildTree()

1) Find index of the maximum element in array. The maximum element must be root of Binary Tree.
2) Create a new tree node ‘root’ with the data as the maximum value found in step 1.
3) Call buildTree for elements before the maximum element and make the built tree as left subtree of ‘root’.
5) Call buildTree for elements after the maximum element and make the built tree as right subtree of ‘root’.
6) return ‘root’.

Implementation: Following is the implementation of the above algorithm.

/* program to construct tree from inorder traversal */

#include<stdio.h>
#include<stdlib.h>

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
    int data;
    struct node* left;
    struct node* right;
};

/* Prototypes of a utility function to get the maximum
   value in inorder[start..end] */
int max(int inorder[], int strt, int end);

/* A utility function to allocate memory for a node */
struct node* newNode(int data);

/* Recursive function to construct binary of size len from
   Inorder traversal inorder[]. Initial values of start and end
   should be 0 and len -1.  */
struct node* buildTree (int inorder[], int start, int end)
{
    if (start > end)
        return NULL;

    /* Find index of the maximum element from Binary Tree */
    int i = max (inorder, start, end);

    /* Pick the maximum value and make it root */
    struct node *root = newNode(inorder[i]);

    /* If this is the only element in inorder[start..end],
       then return it */
    if (start == end)
        return root;

    /* Using index in Inorder traversal, construct left and
       right subtress */
    root->left  = buildTree (inorder, start, i-1);
    root->right = buildTree (inorder, i+1, end);

    return root;
}

/* UTILITY FUNCTIONS */
/* Function to find index of the maximum value in arr[start...end] */
int max (int arr[], int strt, int end)
{
    int i, max = arr[strt], maxind = strt;
    for(i = strt+1; i <= end; i++)
    {
        if(arr[i] > max)
        {
            max = arr[i];
            maxind = i;
        }
    }
    return maxind;
}

/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode (int data)
{
    struct node* node = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return node;
}

/* This funtcion is here just to test buildTree() */
void printInorder (struct node* node)
{
    if (node == NULL)
        return;

    /* first recur on left child */
    printInorder (node->left);

    /* then print the data of node */
    printf("%d ", node->data);

    /* now recur on right child */
    printInorder (node->right);
}

/* Driver program to test above functions */
int main()
{
   /* Assume that inorder traversal of following tree is given
         40
       /   \
      10     30
     /         \
    5          28 */

    int inorder[] = {5, 10, 40, 30, 28};
    int len = sizeof(inorder)/sizeof(inorder[0]);
    struct node *root = buildTree(inorder, 0, len - 1);

    /* Let us test the built tree by printing Insorder traversal */
    printf("\n Inorder traversal of the constructed tree is \n");
    printInorder(root);
    return 0;
}

Output:

Inorder traversal of the constructed tree is

5 10 40 30 28

Time Complexity: O(n^2)

answer Jun 23, 2016 by Manikandan J
I have mentioned in my question above that I want to construct a BST (Binary search tree), as we aware that any right child of the root must be greater and left child must be smaller respectively ,however your tree does not satisfy the properties of BST at all.
...