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.

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