C++ program to construct binary search tree from its given level order traversal














































C++ program to construct binary search tree from its given level order traversal



#include <bits/stdc++.h> 

using namespace std; 

struct Node 
int data; 
Node *left, *right; 
}; 

struct NodePtr 
Node *ptr; 
int min, max; 
}; 
 
Node* getNode(int data) 
Node *newNode = 
(Node*)malloc(sizeof(Node)); 
 
newNode->data = data; 
newNode->left = newNode->right = NULL;  
return newNode; 

// function to construct a BST from its level order traversal 
Node* constructBst(int arr[], int n) 
// if tree is empty 
if (n == 0) 
return NULL; 
Node *root; 
// queue to store NodePtr 
queue<NodePtr> q; 
 
int i=0; 

NodePtr 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; 
 
while (i != n)  
NodePtr temp = q.front(); 
q.pop(); 
if (i < n && (arr[i] < temp.ptr->data && 
arr[i] > temp.min)) 
// Create NodePtr 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;  
if (i < n && (arr[i] > temp.ptr->data && 
arr[i] < temp.max)) 
// Create NodePtr 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; 
}  
 
return root; 
// function to print the inorder traversal 
void inorderTraversal(Node* root) 
if (!root) 
return; 
inorderTraversal(root->left); 
cout << root->data << " "; 
inorderTraversal(root->right);  

int main() 
int n;
cout<<"enter the number of elements:"<<endl;
cin>>n;
int a[n];
        cout<<"enter the elements"<<endl;
for(int i=0;i<n;i++)
cin>>a[i];
Node *root = constructBst(a, n); 
cout << "Inorder Traversal of constructed BST from level order traversal "<<endl; 
inorderTraversal(root); 
return 0;  
// OUTPUT::
//enter the number elements: 
// 7
//20 8 22 4 12 10 14
//output:: Inorder Traversal of constructed BST from level order traversal 
// 4 8 10 12 14 20 22

Comments