Last Updated: 7 Dec, 2020
Construct BST from Level Order
Easy
Asked in companies
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
Approaches
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’
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’.
Similar problems