BST Construction from Level Order Traversal

Given an array called levelOrder consisting of 'N' elements, this array represents the level order traversal of a Binary Search Tree (BST). Your task is to construct the BST from this level order traversal.

Binary Search Tree (BST) Properties:

• The left subtree of a node contains only nodes with data less than the node’s data.
• The right subtree of a node contains only nodes with data greater than the node’s data.
• Both the left and right subtrees must also be binary search trees.

Input:

The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows. The first line of each test case contains a single integer ‘N’ denoting the length of the array. The second line of each test case contains ‘N’ single space-separated integers denoting the elements of the array.

Output:

For each test case, print the inorder traversal of the BST. The inorder traversal of a binary tree is the traversal method in which for any node its left subtree is visited first, then the node itself, and then the right subtree. Print the output of each test case in a separate line.

Example:

Example:

For the given level order traversal: 5 3 6 2 4 7 The BST will be represented such that when traversed inorder it returns: 2 3 4 5 6 7

• Input Example:

T = 1 N = 6 levelOrder = [5, 3, 6, 2, 4, 7]

• Output Example:

2 3 4 5 6 7

Constraints:

• 1 <= T <= 10
• 1 <= N <= 105
• 0 <= levelOrder[i] <= 105
• Time Limit: 1 sec

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.