Construct BST from its given level order traversal

Approach

The problem can be solved recursively. Let us make a list of observations to get started:

1. The first element in the level order traversal must be the root of the BST.
    
2. The second element can either be its left or right child.
    
3. If the second element is less than the root element, it will be the left child, otherwise the right child.
    

We can recursively use the second and third observations to create the BST. For example:

• If an element in the level order traversal is less than the root element, it will be inserted in an appropriate position in the left subtree of the BST created so far.
   
• Similarly, if an element is greater than the root element, it will be inserted in an appropriate position in the right subtree of the root element created so far.
   
• We will recursively call the required function with an updated root element as we filter the subtree to go in each recursive step.
   

Let’s now discuss the algorithm.

Algorithm

1. Create the root node as NULL initially
    
2. Traverse the level order traversal array and for each of its elements, insert the node corresponding to it in the BST.
    
3. There are three conditions encountered when a new node is to be inserted in the BST at any level.
   
   
   1. The root node is NULL → In this case, simply create a new node and make it the root.
       
   2. The value of the node is less or equal to than the array element → Insert a new node in its left subtree. Recursive call to be made for its left subtree.
       
   3. The value of the node is more than the array element → Insert a new node in its right subtree. Recursive call to be made for its right subtree.
       
4. Finally, print the preorder traversal of the BST.

Implementation in C++

// C++ implementation to construct a BST
// from its level order traversal
#include <iostream>
#include <vector>

using namespace std;

// BST Node
class Node
{
    public:
    int data;
    Node *left;
    Node *right;

    Node(int d) {
        data = d;
        left = NULL;
        right = NULL;
    }
};

// Function to create a node and insert it
// at its appropriate position
Node *insertNode(Node *root, int data)
{
    // if root is null, make current element the root
    if (root == NULL)
    {
        root = new Node(data);
        return root;
    }
    // if element is less than root
    if (data <= root->data){
        // insert it into left subtree
        root->left = insertNode(root->left, data);
    }
    // if element is greater than root
    else {
        // attach it into right subtree
        root->right = insertNode(root->right, data);
    }

    // return root
    return root;
}

Node *constructBST(vector<int> levelOrderTraversal)
{
    int n = levelOrderTraversal.size();

    if (n == 0)
        return NULL;

    Node *root = NULL;

    // Insert the elements one by one.
    for (int i = 0; i < n; i++)
        root = insertNode(root, levelOrderTraversal[i]);

    return root;
}

// function to print the preorder traversal
void preOrderTraversal(Node *root)
{
    if (!root)
        return;

    // Standard preorder technique
    cout << root->data << " ";
    preOrderTraversal(root->left);
    preOrderTraversal(root->right);
}

int main()
{
    vector<int> levelOrdTraversal = {12, 4, 13, 3, 6, 14};

    Node *root = constructBST(levelOrdTraversal);

    cout << "PreOrder Traversal: ";
    preOrderTraversal(root);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

PreOrder Traversal: 12 4 3 6 13 14

Time Complexity Analysis

The time of the above approach is O(N^2) where N is the number of nodes in the BST. 

It is because we are inserting each of the elements of the level order traversal one by one in the BST. Each element can take up to O(N) time to find its final position in the BST. Hence, the worst case time complexity can be O(N^2).

Space Complexity Analysis

The space complexity of the above approach is O(N), where N is the number of nodes in the BST. It is because we are taking up extra space to store the nodes of the BST created.

Check out this problem - Mirror A Binary Tree.

Must Read Recursive Binary Search.

Frequently Asked Questions

Is it possible for the inorder traversal sequence and the preorder traversal sequence to be the same?

If the binary tree nodes only had the right child, the inorder and preorder traversal sequences would be the same.

What is the best way to traverse a tree?

The best optimal algorithm is typically one that is adapted to a certain use case and platform. It makes no difference whether you order in advance, preorder, or later. Or whether you play DFS or BFS.

What are the applications of trees?

Trees can be used to store data that has an inherent hierarchical structure. An operating system may, for example, use a tree for directories, files, and folders in its file management system. Because they are dynamic, adding and removing nodes is simple.

What are some of the benefits of employing post-order traversal in a binary tree?

It is employed in order to obtain Reverse Polish Notations.

Conclusion

In this blog, we discussed an interesting problem involving recursion, Binary Search Trees and Level Order Traversals. We discussed the approach involving the key recursive step where we filtered, for each element of the level order traversal, the subtree it will be part of. Finally, we found out that the time complexity of the approach is O(N^2) as we are inserting each element of the level order traversal one by one in the BST created so far.

You can follow these amazing blogs on diverse DSA topics to get a firm hold on Data Structures. To learn, see the traversal of the binary tree, Diagonal Traversal of Binary Tree (Recursive and Iterative), and Specific Level Order Traversal of Binary Tree.

Recommended problems -

• Preorder Traversal
• Zig Zag Tree Traversal 

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and many more! If you want to test your capacity in coding, you may check out the mock test series and participate in the contests hosted on the Coding Ninjas Studio website. But if you have just started learning and are looking for questions asked by tech giants like Amazon, Microsoft, Google, Uber, etc., you must look at the problems, interview experiences, and interview bundle for placement preparations.

You may also consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!