# Construct BST from its given level order traversal

Construct the BST (Binary Search Tree) from its given level order traversal.

Examples:

```Input : arr[] = {7, 4, 12, 3, 6, 8, 1, 5, 10}
Output : BST:
7
/
4   12
/   /
3  6 8
/  /
1   5   10
```

The idea is to use a queue to construct tree. Every element of queue has a structure say NodeDetails which stores details of a tree node. The details are pointer to the node, and two variables min and max where min stores the lower limit for the node values which can be a part of the left subtree and max stores the upper limit for the node values which can be a part of the right subtree for the specified node in NodeDetails structure variable. For the 1st array value arr[0], create a node and then create a NodeDetails structure having pointer to this node and min = INT_MIN and max = INT_MAX. Add this structure variable to a queue. This Node will be the root of the tree. Move to 2nd element in arr[] and then perform the following steps:

1. Pop NodeDetails from the queue in temp.
2. Check whether the current array element can be a left child of the node in temp with the help of min and temp.node data values. If it can, then create a new NodeDetails structure for this new array element value with its proper ‘min’ and ‘max’ values and push it to the queue, make this new node as the left child of temp’s node and move to next element in arr[].
3. Check whether the current array element can be a right child of the node in temp with the help of max and temp.node data values. If it can, then create a new NodeDetails structure for this new array element value with its proper ‘min’ and ‘max’ values and push it to the queue, make this new node as the right child of temp’s node and move to next element in arr[].
4. Repeat steps 1, 2 and 3 until there are no more elements in arr[].

For a left child node, its min value will be its parent’s ‘min’ value and max value will be the data value of its parent node. For a right child node, its min value will be the data value of its parent node and max value will be its parent’s ‘max’ value.

Below is C++ implementation of above approach:

 `// C++ implementation to construct a BST ` `// from its level order traversal ` `#include ` ` `  `using` `namespace` `std; ` ` `  `// node of a BST ` `struct` `Node ` `{ ` `    ``int` `data; ` `    ``Node *left, *right; ` `}; ` ` `  `// to store details of a node like ` `// pointer to the node, 'min' and 'max'  ` `// to obtain the range of values where ` `// node's left and right child's could lie ` `struct` `NodeDetails ` `{ ` `    ``Node *ptr; ` `    ``int` `min, max; ` `}; ` ` `  `// function to get a new node ` `Node* getNode(``int` `data) ` `{ ` `    ``// Allocate memory ` `    ``Node *newNode = ` `        ``(Node*)``malloc``(``sizeof``(Node)); ` `     `  `    ``// put in the data     ` `    ``newNode->data = data; ` `    ``newNode->left = newNode->right = NULL;     ` `    ``return` `newNode; ` `} ` ` `  `// function to construct a BST from ` `// its level order traversal ` `Node* constructBst(``int` `arr[], ``int` `n) ` `{ ` `    ``// if tree is empty ` `    ``if` `(n == 0) ` `        ``return` `NULL; ` `     `  `    ``Node *root; ` `     `  `    ``// queue to store NodeDetails ` `    ``queue q; ` `     `  `    ``// index variable to access array elements ` `    ``int` `i=0; ` `     `  `    ``// node details for the  ` `    ``// root of the BST ` `    ``NodeDetails newNode; ` `    ``newNode.ptr = getNode(arr[i++]); ` `    ``newNode.min = INT_MIN; ` `    ``newNode.max = INT_MAX; ` `    ``q.push(newNode); ` `     `  `    ``// getting the root of the BST ` `    ``root = newNode.ptr; ` `     `  `    ``// until there are no more elements  ` `    ``// in arr[] ` `    ``while` `(i != n)         ` `    ``{ ` `        ``// extracting NodeDetails of a ` `        ``// node from the queue ` `        ``NodeDetails temp = q.front(); ` `        ``q.pop(); ` `         `  `        ``// check whether there are more elements  ` `        ``// in the arr[] and arr[i] can be left child  ` `        ``// of 'temp.ptr' or not  ` `        ``if` `(i < n && (arr[i] < temp.ptr->data &&  ` `                          ``arr[i] > temp.min)) ` `        ``{ ` `            ``// Create NodeDetails for newNode  ` `            ``/// and add it to the queue ` `            ``newNode.ptr = getNode(arr[i++]); ` `            ``newNode.min = temp.min; ` `            ``newNode.max = temp.ptr->data; ` `            ``q.push(newNode); ` `             `  `            ``// make this 'newNode' as left child ` `            ``// of 'temp.ptr' ` `            ``temp.ptr->left = newNode.ptr;             ` `        ``} ` `         `  `        ``// check whether there are more elements  ` `        ``// in the arr[] and arr[i] can be right child  ` `        ``// of 'temp.ptr' or not  ` `        ``if` `(i < n && (arr[i] > temp.ptr->data && ` `                               ``arr[i] < temp.max)) ` `        ``{ ` `            ``// Create NodeDetails for newNode  ` `            ``/// and add it to the queue ` `            ``newNode.ptr = getNode(arr[i++]); ` `            ``newNode.min = temp.ptr->data; ` `            ``newNode.max = temp.max; ` `            ``q.push(newNode); ` `             `  `            ``// make this 'newNode' as right child ` `            ``// of 'temp.ptr' ` `            ``temp.ptr->right = newNode.ptr; ` `        ``}         ` `    ``} ` `     `  `    ``// root of the required BST ` `    ``return` `root; ` `} ` ` `  `// function to print the inorder traversal ` `void` `inorderTraversal(Node* root) ` `{ ` `    ``if` `(!root) ` `        ``return``; ` `     `  `    ``inorderTraversal(root->left); ` `    ``cout << root->data << ``" "``; ` `    ``inorderTraversal(root->right);     ` `} ` ` `  `// Driver program to test above ` `int` `main() ` `{ ` `    ``int` `arr[] = {7, 4, 12, 3, 6, 8, 1, 5, 10}; ` `    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr[0]); ` `     `  `    ``Node *root = constructBst(arr, n); ` `     `  `    ``cout << ``"Inorder Traversal: "``; ` `    ``inorderTraversal(root); ` `    ``return` `0;     ` `}  `

/div>

Output:

```Inorder Traversal: 1 3 4 5 6 7 8 10 12
```

Time Complexity : O(n)