Construct the BST (Binary Search Tree) from its given level order traversal.
Examples:
Input : {7, 4, 12, 3, 6, 8, 1, 5, 10}
Output :
BST:
7
/ \
4 12
/ \ /
3 6 8
/ / \
1 5 10
Approach :
The idea is to make a struct element NodeDetails which contains a pointer to the node, minimum data and maximum data of the ancestor. Now perform the steps as follows:
- Push the root node to the queue of type NodeDetails.
- Extract NodeDetails of a node from the queue and compare them with the minimum and maximum values.
- Check whether there are more elements in the arr[] and arr[i] can be left child of ‘temp.ptr’ or not.
- Check whether there are more elements in the arr[] and arr[i] can be the right child of ‘temp.ptr’ or not.
- End the loop when the queue becomes empty.
Below is the implementation of the above approach:
C++
// C++ program to construct BST// using level order traversal#include <bits/stdc++.h>using namespace std;// Node structure of a binary treestruct Node { int data; Node* right; Node* left; Node(int x) { data = x; right = NULL; left = NULL; }};// Structure formed to store the// details of the ancestorstruct NodeDetails { Node* ptr; int min, max;};// Function for the preorder traversalvoid preorderTraversal(Node* root){ if (!root) return; cout << root->data << " "; // Traversing left child preorderTraversal(root->left); // Traversing right child preorderTraversal(root->right);}// Function to make a new node// and return its pointerNode* getNode(int data){ Node* temp = new Node(0); temp->data = data; temp->left = NULL; temp->right = NULL; return temp;}// Function to construct the BSTNode* constructBst(int arr[], int n){ if (n == 0) return NULL; Node* root; queue<NodeDetails> q; // index variable to // access array elements int i = 0; // Node details for the // root of the BST NodeDetails newNode; newNode.ptr = getNode(arr[i++]); newNode.min = INT_MIN; newNode.max = INT_MAX; q.push(newNode); // Getting the root of the BST root = newNode.ptr; // Until there are no more // elements in arr[] while (i != n) { // Extracting NodeDetails of a // node from the queue NodeDetails temp = q.front(); q.pop(); // Check whether there are more elements // in the arr[] and arr[i] can be // left child of 'temp.ptr' or not if (i < n && (arr[i] < temp.ptr->data && arr[i] > temp.min)) { // Create NodeDetails for newNode // and add it to the queue newNode.ptr = getNode(arr[i++]); newNode.min = temp.min; newNode.max = temp.ptr->data; q.push(newNode); // Make this 'newNode' as left child // of 'temp.ptr' temp.ptr->left = newNode.ptr; } // Check whether there are more elements // in the arr[] and arr[i] can be // right child of 'temp.ptr' or not if (i < n && (arr[i] > temp.ptr->data && arr[i] < temp.max)) { // Create NodeDetails for newNode // and add it to the queue newNode.ptr = getNode(arr[i++]); newNode.min = temp.ptr->data; newNode.max = temp.max; q.push(newNode); // Make this 'newNode' as right // child of 'temp.ptr' temp.ptr->right = newNode.ptr; } } // Root of the required BST return root;}// Driver codeint main(){ int n = 9; int arr[n] = { 7, 4, 12, 3, 6, 8, 1, 5, 10 }; // Function Call Node* root = constructBst(arr, n); preorderTraversal(root); return 0;} |
Java
// JAVA program to construct BST// using level order traversalimport java.io.*;import java.util.*;// Node class of a binary treeclass Node { int data; Node left, right; public Node(int data) { this.data = data; left = right = null; }}// Class formed to store the// details of the ancestorsclass NodeDetails { Node node; int min, max; public NodeDetails(Node node, int min, int max) { this.node = node; this.min = min; this.max = max; }}class GFG { // Function for the preorder traversal public static void preorder(Node root) { if (root == null) return; System.out.print(root.data + " "); // traversing left child preorder(root.left); // traversing right child preorder(root.right); } // Function to construct BST public static Node constructBST(int[] arr, int n) { // creating root of the BST Node root = new Node(arr[0]); Queue<NodeDetails> q = new LinkedList<>(); // node details for the root of the BST q.add(new NodeDetails(root, Integer.MIN_VALUE, Integer.MAX_VALUE)); // index variable to access array elements int i = 1; // until queue is not empty while (!q.isEmpty()) { // extracting NodeDetails of a node from the // queue NodeDetails temp = q.poll(); Node c = temp.node; int min = temp.min, max = temp.max; // checking whether there are more elements in // the array and arr[i] can be left child of // 'temp.node' or not if (i < n && min < arr[i] && arr[i] < c.data) { // make this node as left child of // 'temp.node' c.left = new Node(arr[i]); i++; // create new node details and add it to // queue q.add(new NodeDetails(c.left, min, c.data)); } // checking whether there are more elements in // the array and arr[i] can be right child of // 'temp.node' or not if (i < n && c.data < arr[i] && arr[i] < max) { // make this node as right child of // 'temp.node' c.right = new Node(arr[i]); i++; // create new node details and add it to // queue q.add( new NodeDetails(c.right, c.data, max)); } } // root of the required BST return root; } // Driver code public static void main(String[] args) { int n = 9; int[] arr = { 7, 4, 12, 3, 6, 8, 1, 5, 10 }; // Function Call Node root = constructBST(arr, n); preorder(root); }} |
Python3
# Python program to construct BST# using level order traversal# Node class of a binary treeclass Node: def __init__(self,data): self.data = data self.left = None self.right = None # Class formed to store the# details of the ancestorsclass NodeDetails: def __init__(self ,node, min, Max): self.node = node self.min = min self.max = Max # Function for the preorder traversaldef preorder(root): if (root == None): return print(root.data ,end = " ") # Traversing left child preorder(root.left) # Traversing right child preorder(root.right)# Function to construct BSTdef constructBST(arr, n): # Creating root of the BST root = Node(arr[0]) q = [] # Node details for the root of the BST q.append(NodeDetails(root, -1000000000, 1000000000)) # Index variable to access array elements i = 1 # Until queue is not empty while (len(q) != 0): # Extracting NodeDetails of a node # from the queue temp = q[0] q = q[1:] c = temp.node Min = temp.min Max = temp.max # Checking whether there are more # elements in the array and arr[i] # can be left child of # 'temp.node' or not if (i < n and Min < arr[i] and arr[i] < c.data): # Make this node as left child of # 'temp.node' c.left = Node(arr[i]) i += 1 # Create new node details and add # it to queue q.append(NodeDetails(c.left, Min, c.data)) # Checking whether there are more elements in # the array and arr[i] can be right child of # 'temp.node' or not if (i < n and c.data < arr[i] and arr[i] < Max): # Make this node as right child of # 'temp.node' c.right = Node(arr[i]) i += 1 # Create new node details and add it to # queue q.append(NodeDetails(c.right, c.data, Max)) # Root of the required BST return root# Driver coden = 9arr = [ 7, 4, 12, 3, 6, 8, 1, 5, 10 ]# Function Callroot = constructBST(arr, n)preorder(root)# This code is contributed by shinjanpatra |
C#
// C# program to construct BST// using level order traversalusing System;using System.Collections.Generic;// Node class of a binary treepublic class Node{ public int data; public Node left, right; public Node(int data) { this.data = data; left = right = null; }}// Class formed to store the// details of the ancestorspublic class NodeDetails{ public Node node; public int min, max; public NodeDetails(Node node, int min, int max) { this.node = node; this.min = min; this.max = max; }}class GFG{// Function for the preorder traversalpublic static void preorder(Node root){ if (root == null) return; Console.Write(root.data + " "); // Traversing left child preorder(root.left); // Traversing right child preorder(root.right);}// Function to construct BSTpublic static Node constructBST(int[] arr, int n){ // Creating root of the BST Node root = new Node(arr[0]); Queue<NodeDetails> q = new Queue<NodeDetails>(); // Node details for the root of the BST q.Enqueue(new NodeDetails(root, int.MinValue, int.MaxValue)); // Index variable to access array elements int i = 1; // Until queue is not empty while (q.Count != 0) { // Extracting NodeDetails of a node // from the queue NodeDetails temp = q.Dequeue(); Node c = temp.node; int min = temp.min, max = temp.max; // Checking whether there are more // elements in the array and arr[i] // can be left child of // 'temp.node' or not if (i < n && min < arr[i] && arr[i] < c.data) { // Make this node as left child of // 'temp.node' c.left = new Node(arr[i]); i++; // Create new node details and add // it to queue q.Enqueue(new NodeDetails(c.left, min, c.data)); } // Checking whether there are more elements in // the array and arr[i] can be right child of // 'temp.node' or not if (i < n && c.data < arr[i] && arr[i] < max) { // Make this node as right child of // 'temp.node' c.right = new Node(arr[i]); i++; // Create new node details and add it to // queue q.Enqueue( new NodeDetails(c.right, c.data, max)); } } // Root of the required BST return root;}// Driver codepublic static void Main(String[] args){ int n = 9; int[] arr = { 7, 4, 12, 3, 6, 8, 1, 5, 10 }; // Function Call Node root = constructBST(arr, n); preorder(root);}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript program to construct BST// using level order traversal// Node class of a binary treeclass Node{ constructor(data) { this.data = data; this.left = null; this.right = null; }}// Class formed to store the// details of the ancestorsclass NodeDetails{ constructor(node, min, max) { this.node = node; this.min = min; this.max = max; }}// Function for the preorder traversalfunction preorder(root){ if (root == null) return; document.write(root.data + " "); // Traversing left child preorder(root.left); // Traversing right child preorder(root.right);}// Function to construct BSTfunction constructBST(arr, n){ // Creating root of the BST var root = new Node(arr[0]) var q = []; // Node details for the root of the BST q.push(new NodeDetails(root, -1000000000, 1000000000)); // Index variable to access array elements var i = 1; // Until queue is not empty while (q.length != 0) { // Extracting NodeDetails of a node // from the queue var temp = q.shift(); var c = temp.node; var min = temp.min, max = temp.max; // Checking whether there are more // elements in the array and arr[i] // can be left child of // 'temp.node' or not if (i < n && min < arr[i] && arr[i] < c.data) { // Make this node as left child of // 'temp.node' c.left = new Node(arr[i]); i++; // Create new node details and add // it to queue q.push(new NodeDetails(c.left, min, c.data)); } // Checking whether there are more elements in // the array and arr[i] can be right child of // 'temp.node' or not if (i < n && c.data < arr[i] && arr[i] < max) { // Make this node as right child of // 'temp.node' c.right = new Node(arr[i]); i++; // Create new node details and add it to // queue q.push( new NodeDetails(c.right, c.data, max)); } } // Root of the required BST return root;}// Driver codevar n = 9;var arr = [ 7, 4, 12, 3, 6, 8, 1, 5, 10 ];// Function Callvar root = constructBST(arr, n);preorder(root);// This code is contributed by noob2000</script> |
Output:
7 4 3 1 6 5 12 8 10
Time Complexity: O(N)
Auxiliary Space: O(N) due to queue data structure
Recursive Approach:
Below is the recursion methods to construct BST.
C++
// C++ implementation to construct a BST// from its level order traversal#include<bits/stdc++.h>using namespace std;// Node* of a BSTstruct Node{ int data; Node* left; Node* right; Node(int data) { this->data = data; this->left = NULL; this->right = NULL; }}; Node* root; // Function to print the inorder traversalvoid preorderTraversal(Node* root) { if (root == NULL) return; cout<<(root->data) << " "; preorderTraversal(root->left); preorderTraversal(root->right);} // Function to get a new Node*Node* getNode(int data){ // Allocate memory Node* node = new Node(data); return node;} // Function to construct a BST from// its level order traversalNode* LevelOrder(Node* root, int data){ if (root == NULL) { root = getNode(data); return root; } if (data <= root->data) root->left = LevelOrder(root->left, data); else root->right = LevelOrder(root->right, data); return root;} Node* constructBst(int arr[], int n){ if (n == 0) return NULL; root = NULL; for(int i = 0; i < n; i++) root = LevelOrder(root, arr[i]); return root;} // Driver codeint main(){ int arr[] = { 7, 4, 12, 3, 6, 8, 1, 5, 10 }; int n = sizeof(arr)/sizeof(arr[0]); // Function Call root = constructBst(arr, n); preorderTraversal(root); return 0;}// This code is contributed by pratham76 |
Java
// Java implementation to construct a BST// from its level order traversalclass GFG{// Node of a BSTstatic class Node{ int data; Node left; Node right; Node(int data) { this.data = data; this.left = null; this.right = null; }};static Node root;// Function to print the inorder traversalstatic void preorderTraversal(Node root) { if (root == null) return; System.out.print(root.data + " "); preorderTraversal(root.left); preorderTraversal(root.right);}// Function to get a new nodestatic Node getNode(int data){ // Allocate memory Node node = new Node(data); return node;}// Function to construct a BST from// its level order traversalstatic Node LevelOrder(Node root, int data){ if (root == null) { root = getNode(data); return root; } if (data <= root.data) root.left = LevelOrder(root.left, data); else root.right = LevelOrder(root.right, data); return root;}static Node constructBst(int []arr, int n){ if (n == 0) return null; root = null; for(int i = 0; i < n; i++) root = LevelOrder(root, arr[i]); return root;}// Driver codepublic static void main(String[] args){ int[] arr = { 7, 4, 12, 3, 6, 8, 1, 5, 10 }; int n = arr.length; // Function Call root = constructBst(arr, n); preorderTraversal(root);}}// This code is contributed by shikhasingrajput |
Python3
# Python3 implementation to construct a BST# from its level order traversalimport math# node of a BSTclass Node: def __init__(self, data): self.data = data self.left = None self.right = None# function to print the inorder traversaldef preorderTraversal(root): if (root == None): return None print(root.data, end=" ") preorderTraversal(root.left) preorderTraversal(root.right)# function to get a new nodedef getNode(data): # Allocate memory newNode = Node(data) # put in the data newNode.data = data newNode.left = None newNode.right = None return newNode# function to construct a BST from# its level order traversaldef LevelOrder(root, data): if(root == None): root = getNode(data) return root if(data <= root.data): root.left = LevelOrder(root.left, data) else: root.right = LevelOrder(root.right, data) return rootdef constructBst(arr, n): if(n == 0): return None root = None for i in range(0, n): root = LevelOrder(root, arr[i]) return root# Driver codeif __name__ == '__main__': arr = [7, 4, 12, 3, 6, 8, 1, 5, 10] n = len(arr) # Function Call root = constructBst(arr, n) root = preorderTraversal(root)# This code is contributed by Srathore |
C#
// C# implementation to construct a BST// from its level order traversalusing System;class GFG{// Node of a BSTpublic class Node{ public int data; public Node left; public Node right; public Node(int data) { this.data = data; this.left = null; this.right = null; }};static Node root;// Function to print the inorder traversalstatic void preorderTraversal(Node root) { if (root == null) return; Console.Write(root.data + " "); preorderTraversal(root.left); preorderTraversal(root.right);}// Function to get a new nodestatic Node getNode(int data){ // Allocate memory Node node = new Node(data); return node;}// Function to construct a BST from// its level order traversalstatic Node LevelOrder(Node root, int data){ if (root == null) { root = getNode(data); return root; } if (data <= root.data) root.left = LevelOrder(root.left, data); else root.right = LevelOrder(root.right, data); return root;}static Node constructBst(int []arr, int n){ if (n == 0) return null; root = null; for(int i = 0; i < n; i++) root = LevelOrder(root, arr[i]); return root;}// Driver codepublic static void Main(string[] args){ int[] arr = { 7, 4, 12, 3, 6, 8, 1, 5, 10 }; int n = arr.Length; // Function Call root = constructBst(arr, n); preorderTraversal(root);}}// This code is contributed by rutvik_56 |
Javascript
<script>// JavaScript implementation to construct a BST// from its level order traversal// Node of a BSTclass Node{ constructor(data) { this.data = data; this.left = null; this.right = null; }} let root; // Function to print the inorder traversalfunction preorderTraversal(root) { if (root == null) return; document.write(root.data," "); preorderTraversal(root.left); preorderTraversal(root.right);} // Function to get a new Node*function getNode(data){ // Allocate memory let node = new Node(data); return node;} // Function to construct a BST from// its level order traversalfunction LevelOrder(root,data){ if (root == null) { root = getNode(data); return root; } if (data <= root.data) root.left = LevelOrder(root.left, data); else root.right = LevelOrder(root.right, data); return root;} function constructBst(arr, n){ if (n == 0) return null; root = null; for(let i = 0; i < n; i++) root = LevelOrder(root, arr[i]); return root;} // Driver codelet arr = [ 7, 4, 12, 3, 6, 8, 1, 5, 10 ]; let n = arr.length; // Function Callroot = constructBst(arr, n);preorderTraversal(root);// code is contributed by shinjanpatra</script> |
Output:
7 4 3 1 6 5 12 8 10
Time Complexity for Python Code O(N log(N))
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
