Problem Statement:
You are given an array of integers in pre-order fashion.
Then you need to check if it is a valid BST.
Solution
pre-order means, root element, followed by left sub-tree, followed by right sub-tree.
First we will construct a BST from the given sequence.
Then we compare the pre-order traversal of the constructed BST with the given array.
Solution in C++
#include<iostream> #include<vector> #include<string> #include<unordered_set> using namespace std; struct Node { int data; struct Node *left, *right; }; Node *get_new_node(int item) { Node *temp = new Node; temp->data = item; temp->left = temp->right = NULL; return temp; } Node* insert_into_bst(Node* node, int data) { if (node == NULL) return get_new_node(data); if (data < node->data) node->left = insert_into_bst(node->left, data); else if (data > node->data) node->right = insert_into_bst(node->right, data); return node; } Node* construct_BST(vector<int> const &seq) { Node* root = nullptr; for (int key: seq) { root = insert_into_bst(root, key); } return root; } bool compare_PreOrder(Node* root, vector<int> const &seq, int &index) { // base case if (root == nullptr) { return true; } if (seq[index] != root->data) { return false; } index++; return compare_PreOrder(root->left, seq, index) && compare_PreOrder(root->right, seq, index); } bool check_is_pre_order_is_BST(vector<int> const &seq) { Node* root = construct_BST(seq); int index = 0; return compare_PreOrder(root, seq, index) && index == seq.size(); } int main() { vector<int> seq = { 1, 2, 30, 4, 5, 6 }; if (check_is_pre_order_is_BST(seq)) { cout << "Array is a BST"; } else { cout << "Array is not a BST"; } return 0; }
Output:
Array is a BST