Construct BST from Level Order
You have been given an array ‘levelOrder’ consisting of ‘N’ elements. The array represents the level order traversal of a Binary Search Tree(BST). You need to construct the BST from this level order traversal.

A Binary Search Tree (BST) is a binary tree data structure that has the following 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.

For Example:

For the given level order traversal: 5 3 6 2 4 7 The BST will be:

The Inorder Traversal of this BST is 2 3 4 5 6 7.

Input Format:

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 Format:

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.

Note:

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

Constraints:

1

Question

Construct BST from Level Order

You have been given an array ‘levelOrder’ consisting of ‘N’ elements. The array represents the level order traversal of a Binary Search Tree(BST). You need to construct the BST from this level order traversal.

A Binary Search Tree (BST) is a binary tree data structure that has the following 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.

For Example:

For the given level order traversal: 5 3 6 2 4 7 

The BST will be:

The Inorder Traversal of this BST is 2 3 4 5 6 7.

Input Format:

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 Format:

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.

Note:

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

Constraints:

1 <= T <= 10
1 <= N <= 10^5
0 <= levelOrder[i] <= 10^5

Time Limit: 1 sec

Accepted Answer

Using Recursion

The basic idea is that for every number we will find its position in BST using recursion.

Algorithm

Let “insertNode” be the recursive function that takes ‘root’ of tree(initially NULL) and the element to be added in BST as input parameters and insert the given element to the BST.
Traverse the given array using a variable ‘i’ and insert each element into BST using “insertNode” function.
Now, the “insertNode” function will work as follows:
- If the root is NULL, then insert the element at the root position.
- Else if the data of the root is greater than the element.
  - Insert element to the left subtree by recursively calling “insertNode” for the left child of the root.
- Else if the data of the root is smaller than the element.
  - Insert element to the right subtree by recursively calling “insertNode” for the right child of the root.
Return ‘root’

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in the Binary Search Tree.

In the worst case (skewed trees), all the nodes of the BST will be in the recursion stack. Therefore the space complexity is O(N).

Time Complexity: O(n^2)Explanation:

O(N^2), where ‘N’ is the number of nodes in the Binary Search Tree.

In the worst case(skewed trees), we are traversing the whole BST while inserting each element. Hence, the time complexity is O(N^2).

Python (3.5)

"""
    Time Complexity : O(N^2)
    Space Complexity : O(N)

    where 'N' is the number of nodes in the BST.
"""

class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def insertNode( root,  data):

	
	# If root is None, insert new node at the root.
    if(root == None):
    
        root = BinaryTreeNode(data)
        return root
    
    
    # If data < data of root, recur for left subtree.
    if (root . data > data):
    
        root . left = insertNode(root . left, data)
    
    
    # Otherwise If data > data of root, recur for right subtree.
    else:
    
        root . right = insertNode(root . right, data)
    

    return root

def constructBst( levelOrder):

    root = None
    
    # Iterating through all numbers.
    for i in range(len(levelOrder)):
    
    	# Recursive function to insert node in BST.
        root = insertNode(root, levelOrder[i])
    

    return root

Java (SE 1.8)

/*

    Time Complexity : O(N ^ 2)

    Space Complexity : O(N)



    where 'N' is the number of nodes in the BST.

*/



import java.util.ArrayList;



public class Solution {



    public static BinaryTreeNode insertNode(BinaryTreeNode root, int data) {



        // If root is null, insert new node at the root.

        if (root == null) {

            root = new BinaryTreeNode(data);

            return root;

        }



        // If data < data of root, recur for left subtree.

        if (root.data > data) {

            root.left = insertNode(root.left, data);

        }



        // Otherwise If data > data of root, recur for right subtree.

        else {

            root.right = insertNode(root.right, data);

        }



        return root;

    }



    public static BinaryTreeNode constructBst(ArrayList levelOrder) {

        BinaryTreeNode root = null;



        // Iterating through all numbers.

        for (int i = 0; i < levelOrder.size(); i++) {

            // Recursive function to insert node in BST.

            root = insertNode(root, levelOrder.get(i).intValue());

        }



        return root;

    }



}

C++ (g++ 5.4)

/*

    Time Complexity : O(N^2)

    Space Complexity : O(N)



    where 'N' is the number of nodes in the BST.

*/





BinaryTreeNode* insertNode(BinaryTreeNode* root, int data)

{

	

	// If root is NULL, insert new node at the root.

    if(root == NULL)

    {

        root = new BinaryTreeNode(data);

        return root;

    }

    

    // If data < data of root, recur for left subtree.

    if (root -> data > data)

    {

        root -> left = insertNode(root -> left, data);

    }

    

    // Otherwise If data > data of root, recur for right subtree.

    else

    {

        root -> right = insertNode(root -> right, data);

    }



    return root;

}



BinaryTreeNode* constructBst(vector& levelOrder)

{

    BinaryTreeNode* root = NULL;

    

    // Iterating through all numbers.

    for (int i = 0; i < levelOrder.size(); i++)

    {

    	// Recursive function to insert node in BST.

        root = insertNode(root, levelOrder[i]);

    }



    return root;

}

Accepted Answer

Optimized Approach

We will create a class ‘NodeRange’ that has:

‘ptr’, representing a pointer to the node.
‘leftRange’, representing the minimum value of any of its child node.
‘rightRange’, representing the maximum value of any of its child node.

Algorithm

Create a queue ‘q’ that stores objects of class ‘NodeRange’.
Push an object of class NodeRange in the queue with ‘ptr’ denoting pointer to the node of BST having data equal to the first element of the array, INT_MAX as ‘rightRange’ and INT_MIN as ‘leftRange’.
Initialize a pointer ‘root’ and store pointer pointing to node with data value levelOrder[0].
Iterate through the array ‘levelOrder’ using a variable ‘i’ with initial value 1.
- Store the object at the front of the queue in ‘rem’ and pop it.
- If node whose pointer is stored in ‘rem’ has value more than levelorder[i] and levelOrder[i] > leftRange stored in ‘rem’.
  - Create an object ‘node’ with ‘ptr’ pointing to a node with data value levelOrder[i], leftRange as leftRange of ‘rem’ and rightRange as data of node that is pointed by ‘rem’.
  - Add ‘node’ to ‘q’
  - Make the node with value levelorder[i] as the left child of the node pointed by the pointer in ‘rem’
  - Increment ‘i’ by 1.
- If node whose pointer is stored in ‘rem’ has value less than levelorder[i] and levelOrder[i] < rightRange stored in ‘rem’.
  - Create an object ‘node’ with ‘ptr’ pointing to a node with data value levelOrder[i], rightRange as rightRange of ‘rem’ and leftRange as data of node that is pointed by ‘rem’.
  - Add ‘node’ to ‘q’
  - Make the node with value levelorder[i] as the right child of the node pointed by the pointer in ‘rem’
  - Increment ‘i’ by 1.
Return ‘root’.

Space Complexity: O(n)Explanation:

O(N), where N is the number of nodes in the Binary Search Tree.

In the worst case(skewed trees), the size of the queue can be O(N). Hence, space complexity is linear.

Time Complexity: O(n)Explanation: