Construct Binary Search Tree From In-order and Pre-order List

Input       : 4  8  3  7  2  6  1  5
Pre-order: 4 3   2  1  8  7  6  5 
In-Order  : 1  2  3  4  5  6  7  8 

Step 1:
In pre-order traversal, we first traverse the root node, then left sub-tree and then right sub tree.  So, the first data in pre-order traversal gives us root.

4 is the root.

In inorder traversal, we first traverse the left sub tree, then root and then right sub tree.  So, the data present on the left side of 4 forms the left sub tree and the data present on the right side of 4 forms the right sub tree

Example:    1   2   3 (left sub tree)         4(root)       5    6  7   8(right sub tree)

                                  4
                               /       \
          Inorder: 1 2 3      In: 5 6 7 8   
        preorder: 3 2 1    pre: 8 7 6 5


Step 2: 
3 is the root of left sub tree
Then, data present on the left side of 3 forms left sub tree.

1   2(left sub tree)    3(root)

Similarly, 8 is the root of right sub tree
Data present on the left side of 8 forms left sub tree.
5  6   7(left sub tree)    8(root)

                                   4
                               /        \
                             3           8
                           /            /
                  In: 1  2    In: 5 6 7
                Pre: 2  1  Pre: 7 6 5

Step 3:
2 is the root of the left sub tree of 3
Data present on the left side of 2 forms left sub tree.
1(left sub tree)    2(root of left sub tree of 3)


Similarly, 7 is the root of left sub tree of 8
Data present on the left side of 7 forms left sub tree.
5 6(left sub tree)    7(root of left sub tree of 8)
                                    4
                                 /      \
                               3         8
                             /           /
                           2           7
                          /           /
                         1       In: 5 6
                                Pre: 6 5

Step 4:
6 is the root of left sub tree of 7
Data present at the left side of 6 forms left sub tree
5(left sub tree)  6(root of left sub tree of 7)
                                    4
                                 /      \
                               3         8
                             /           /
                           2           7
                          /           /
                         1          6
                                   /
                                  5

See Also:
C Program To Represent Binary Search Tree Using Arrays
C Program To Perform Insertion, Deletion and Traversal In Binary Search Tree
C Program To Implement Binary Tree Traversals: In-order, Pre-order and Post-order
C Program To Implement Dictionary Using Binary Search Tree
C Program To Perform Searching in Binary Search Tree

C Program To Perform Insertion, Deletion & Traversal In Threaded BST

C Program To Perform Insertion, Deletion And Traversal In Red Black Tree
C Program To Perform Insertion, Deletion and Traversal in AVL Tree
C Program To Perform Insertion, Deletion and Traversal In B-Tree
C Program To Implement Priority Queue Using Binary Heaps
Construct Binary Search Tree From In-order and Pre-order Traversal Outputs

C Program To Construct Binary Search Tree From In-order & Pre-order List:

---

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

  struct bstNode {
        int value;
        struct bstNode *left, *right;
  };

  struct bstNode *root = NULL;
  int *preOrder, *inOrder, count = 0;

  /* creating node of the tree  and fill the given value */
  struct bstNode * createNode(int value) {
        struct bstNode *childNode;
        childNode  = (struct bstNode *) malloc(sizeof(struct bstNode));
        childNode->value = value;
        childNode->left = NULL;
        childNode->right = NULL;
        return (childNode);
  }

  /* inserting a new node into the tree */
  void bstInsert(struct bstNode **node, int value) {
        if (!*node) {
                *node = createNode(value);
        } else if (value < (*node)->value) {
                /* value less than parent - insert in left subtree */
                bstInsert(&(*node)->left, value);
        } else if (value > (*node)->value) {
                /* value greater than parent - insert in right subtree */
                bstInsert(&(*node)->right, value);
        }
  }

  /* pre order tree traversal */

  void pre_order(struct bstNode *node) {

        if (node) {

                preOrder[count++] = node->value;

                printf("%d ", node->value);

                pre_order(node->left);

                pre_order(node->right);

        }

        return;

  }

  /* inorder tree traversal */

  void in_order(struct bstNode *node) {

        if (node) {

                in_order(node->left);

                inOrder[count++] = node->value;

                printf("%d ", node->value);

                in_order(node->right);

        }

        return;

  }

  void traversal() {

        count = 0;

        printf("Pre-order:");

        pre_order(root);

        count = 0;

        printf("\nIn-Order:");

        in_order(root);

        printf("\n");

  }

  /* delete Binary Search Tree */

  struct bstNode * deleteBST(struct bstNode *myNode) {

        if (myNode) {

                deleteBST(myNode->left);

                deleteBST(myNode->right);

                free(myNode);

                myNode = NULL;

        }

        return (myNode);

  }

  struct bstNode * reconstructBST(int *inorder, int *preorder, int n) {

        struct bstNode *myNode, *lchild, *rchild;

        int i, j, in[100], pre[100];

        if (!n) {

                return NULL;

        }

        /* create root node */

        myNode = createNode(preorder[0]);

        if (n == 1) {

                return myNode;

        }

        /* move to the root node in inorder data */

        for (i = 0; inorder[i] != preorder[0]; i++);

        if (i > 0) {

                /* left sub-tree from in-order array */

                for (j = 0; j <= i; j++)

                        in[j] = inorder[j];

                /* left sub-tree from pre-order array */

                for (j = 0; j < i; j++)

                        pre[j] = preorder[j + 1];

        }

        /* get the left child */

        lchild = reconstructBST(in, pre, i);

        myNode->left = lchild;

        if (i < n - 1) {

                for (j = i; j < n - 1; j++) {

                        /* right subtree */

                        in[j - i] = inorder[j + 1];

                        pre[j - i] = preorder[j + 1];

                }

        }

        /* get the right child */

        rchild = reconstructBST(in, pre, n - i - 1);

        myNode->right = rchild;

        return myNode;

  }

  int main() {

        int value, i, n;

        printf("Enter the no of nodes:");

        scanf("%d", &n);

        preOrder = (int *) calloc(sizeof (int), n);

        inOrder = (int *) calloc(sizeof (int), n);

        for (i = 0; i < n; i++) {

                printf("Enter your input %d:", i + 1);

                scanf("%d", &value);

                bstInsert(&root, value);

        }

        traversal();

        printf("\n\n");

        root = deleteBST(root);

        root = reconstructBST(inOrder, preOrder, n);

        printf("After reconstruct BST from inorder and preorder data:\n");

        traversal();

        printf("\n\n");

        return 0;

  }

  Output: (Reconstruct BST From In-order & Pre-order List - C Program)

  jp@jp-VirtualBox:~/$ ./a.out
  Enter the no of nodes:8
  Enter your input 1:4
  Enter your input 2:8
  Enter your input 3:3
  Enter your input 4:7
  Enter your input 5:2
  Enter your input 6:6
  Enter your input 7:1
  Enter your input 8:5

  Pre-order:4 3 2 1 8 7 6 5 
  In-Order:1 2 3 4 5 6 7 8 

  After reconstruct BST from inorder and preorder data:
  Pre-order:4 3 2 1 8 7 6 5 
  In-Order:1 2 3 4 5 6 7 8