Lecture 304:- Program for Generating BST from Preorder

Here's a C++ program to generate a Binary Search Tree (BST) from a given Preorder traversal:

cppCopy code

#include <iostream> #include <vector> using namespace std; struct TreeNode {    int val;    TreeNode* left;    TreeNode* right;    TreeNode(int data) : val(data), left(nullptr), right(nullptr) {} }; // Recursive function to construct BST from Preorder traversal TreeNode* constructBST(vector<int>& preorder, int& index, int minValue, int maxValue) {    if (index >= preorder.size() || preorder[index] < minValue || preorder[index] > maxValue)        return nullptr;    TreeNode* root = new TreeNode(preorder[index++]);    root->left = constructBST(preorder, index, minValue, root->val - 1);    root->right = constructBST(preorder, index, root->val + 1, maxValue);    return root; } // Function to construct BST from Preorder traversal TreeNode* constructBST(vector<int>& preorder) {    int index = 0;    return constructBST(preorder, index, INT_MIN, INT_MAX); } // Function for in-order traversal (used for verification) void inOrderTraversal(TreeNode* root) {    if (root == nullptr)        return;    inOrderTraversal(root->left);    cout << root->val << " ";    inOrderTraversal(root->right); } int main() {    vector<int> preorder = {8, 5, 3, 7, 10, 9, 12};    // Construct BST from the given Preorder traversal    TreeNode* root = constructBST(preorder);    // Perform in-order traversal to verify the BST    cout << "In-order Traversal of BST: ";    inOrderTraversal(root);    cout << endl;    // Remember to free the allocated memory after use to avoid memory leaks.    // You can implement a function to delete the entire tree if needed.    return 0; }

Output:

cssCopy code

In-order Traversal of BST: 3 5 7 8 9 10 12

In this program, we use the constructBST function to build the BST recursively. The function takes a vector preorder containing the Preorder traversal of the BST. It also uses an index to keep track of the current node being processed. The function returns the constructed BST. The in-order traversal is performed to verify the correctness of the generated BST.