Home » Technical Interview Questions » Tree Interview Questions » Construct BST from its given Level Order Traversal

Construct BST from its given Level Order Traversal


Reading Time - 6 mins

Given the level order traversal of a Binary Search Tree, write an algorithm to construct the Binary Search Tree or BST from ITS given level order traversal.

Example

Input
levelOrder[] = {18, 12, 20, 8, 15, 25, 5, 9, 22, 31}
Output

Construct BST from its given Level Order Traversal

In-order : 5 8 9 12 15 18 20 22 25 31

Input
levelOrder[] = {4, 2, 5, 1, 3, 6}
Output

Construct BST from its given Level Order Traversal

In-order : 1 2 3 4 5 6

Algorithm for constructing BST from level order traversal

The first element in the level order traversal always forms the root of the Binary Search Tree. The next value may form the left node or the right node depending on its value.

If the next node is smaller than root than it will be inserted to the left of the root, else it will be inserted to the right.
The idea is as follows, if the root of BST is null, form the current element is smaller than the root, then insert it at the appropriate position in the left sub-tree of the root, else insert it inappropriate position in the right subtree of root.

  1. Initialize the root of BST as null. If there are no elements in the level order traversal, return root.
  2. For every element in the levelOrder array, repeat steps 3, 4, and 5.
  3. If the root is null, make the current element as the root.
  4. Else if the current element is less than root, go to step 3, the root becomes root.left and the element remains the same.
  5. Else if the current element is greater than root, go to step 3, the root becomes root.right and the element remains the same.
  6. Return root.
READ  BST to a Tree with Sum of all Smaller Keys

JAVA Code for constructing BST from level order traversal

public class ConstructBSTFromItsGivenLevelOrderTraversal {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    // function to print in order traversal of a binary tree
    private static void inorder(Node root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.data + " ");
            inorder(root.right);
        }
    }

    private static Node attachNode(Node root, int value) {
        // if root is null, make the current element as root
        if (root == null) {
            root = new Node(value);
            return root;
        }

        // if element is less than root
        if (value < root.data) {
            // attach it to left subtree
            root.left = attachNode(root.left, value);
        } else {
            // attach it to right subtree
            root.right = attachNode(root.right, value);
        }

        // return root
        return root;
    }

    private static Node formBST(int[] levelOrder) {
        // initialize root as null
        Node root = null;

        // for each element attach the node to required position in the BST
        for (int i = 0; i < levelOrder.length; i++) {
            // Step 3 to 5
            root = attachNode(root, levelOrder[i]);
        }

        // return root
        return root;
    }

    public static void main(String[] args) {
        // Example 1
        int levelOrder1[] = new int[] {18, 12, 20, 8, 15, 25, 5, 9, 22, 31};
        Node root1 = formBST(levelOrder1);
        inorder(root1);
        System.out.println();

        // Example 2
        int levelOrder2[] = new int[] {4, 2, 5, 1, 3, 6};
        Node root2 = formBST(levelOrder2);
        inorder(root2);
        System.out.println();
    }
}
5 8 9 12 15 18 20 22 25 31 
1 2 3 4 5 6

C++ Code for constructing BST from level order traversal

#include <iostream> 
#include<vector> 
#include<queue> 
using namespace std; 

// class representing node of a binary tree 
class Node { 
    public: 
    int data; 
    Node *left; 
    Node *right; 
    
    Node(int d) { 
        data = d; 
        left = right = NULL; 
    } 
}; 

// function to print the in-order traversal of a binary tree 
void inOrder(Node *root) { 
    if (root != NULL) { 
        inOrder(root->left); 
        cout<<root->data<<" "; 
        inOrder(root->right); 
    } 
} 

Node* attachNode(Node *root, int value) {
    // if root is null, make the current element as root
    if (root == NULL) {
        root = new Node(value);
        return root;
    }
    
    // if element is less than root
    if (value < root->data) {
        // attach it to left subtree
        root->left = attachNode(root->left, value);
    } else {
        // attach it to right subtree
        root->right = attachNode(root->right, value);
    }
    
    // return root
    return root;
}

Node* formBST(int *levelOrder, int n) {
    // initialize root as null
    Node *root = NULL;
    
    // for each element attach the node to required position in the BST
    for (int i = 0; i < n; i++) {
        // Step 3 to 5
        root = attachNode(root, levelOrder[i]);
    }
    
    // return root
    return root;
}

int main() { 
    // Example 1
    int levelOrder1[] = {18, 12, 20, 8, 15, 25, 5, 9, 22, 31};
    Node *root1 = formBST(levelOrder1, sizeof(levelOrder1) / sizeof(levelOrder1[0]));
    inOrder(root1);
    cout<<endl;

    // Example 2
    int levelOrder2[] = {4, 2, 5, 1, 3, 6};
    Node *root2 = formBST(levelOrder2, sizeof(levelOrder2) / sizeof(levelOrder2[0]));
    inOrder(root2);
    cout<<endl;
    
    return 0; 
}
5 8 9 12 15 18 20 22 25 31 
1 2 3 4 5 6

Complexity Analysis

Time Complexity = O(n2)
Space Complexity = O(n), due to recursion
where n is the total number of elements in the level order array.

READ  Types of Binary Tree

Reference1     reference2

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions