> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/trees/untitled-1.md).

# Convert Level Order Traversal to BST

Given an array of size **N** containing level order traversal of a **BST**. The task is to complete the function **constructBst()**, that construct the BST (Binary Search Tree) from its given level order traversal.

**Input:**\
First line of input contains number of testcases T. For each testcase, first line contains number of elements and next line contains n elements which is level order travesal of a BST.

**Output:**\
For each test return the pointer to the root of the newly constructed BST.

**User Task:**\
Your task is to complete the function **constructBst**() which has two arguments, first as the array containing level order traversal of BST and next argument as the length of array.

**Expected Time Complexity:** O(N)\
**Expected Auxiliary Space:** O(N).

**Constraints:**\
1 <= T <= 100\
1 <= N <= 103

**Example:**\
**Input:**\
2\
9\
7 4 12 3 6 8 1 5 10\
6\
1 3 4 6 7 8

**Output:**\
7 4 3 1 6 5 12 8 10\
1 3 4 6 7 8

**Explanation:**\
**Testcase 1:** After constructing BST, the preorder traversal of BST is 7 4 3 1 6 5 12 8 10.\
**Testcase 2:** After constructing BST, the preorder traversal of BST is 1 3 4 6 7 8.

```java
class GFG {
    static class Pair {
        Node root;
        int lowerBound, upperBound;

        Pair(Node root, int lower, int upper) {
            this.root = root;
            lowerBound = lower;
            upperBound = upper;
        }
    }

    public Node constructBST(int[] arr) {
        int n = arr.length;
        Node root = new Node(arr[0]);
        int index = 1;
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(root, Integer.MIN_VALUE, Integer.MAX_VALUE));
        while (q.size() != 0) {
            int size = q.size();
            boolean end = false;
            while (size-- > 0) {
                Pair node = q.poll();
                if (index < arr.length && arr[index] >= node.lowerBound && arr[index] < node.root.data) {
                    node.root.left = new Node(arr[index++]);
                    q.add(new Pair(node.root.left, node.lowerBound, node.root.data - 1));
                }
                if (index < arr.length && arr[index] > node.root.data && arr[index] <= node.upperBound) {
                    node.root.right = new Node(arr[index++]);
                    q.add(new Pair(node.root.right, node.root.data + 1, node.upperBound));
                }
                if (index == arr.length) {
                    end = true;
                    break;
                }
            }
            if (end)
                break;
        }
        return root;
    }
}
```