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