> 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;
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/trees/untitled-1.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.