Binary Search Trees: Check if the pre-order is a valid BST

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