BST Checker always returning true

[dbarclay100]

Im checking to see if an array is a BST. Im not sure why my isBST() which calls CheckIfBST() is always returning true. Is it my logic for CheckIfBST()?

I tried "2 4 5"

bst_validator.cpp

Any Help is Appreciated!

#include <iostream> 
#include <string> 
#include <limits>
#include <sstream> 
#include <vector>

// C++ implementation to check if the given array 
// can represent Level Order Traversal of Binary 
// Search Tree 

using namespace std; 

#include<iostream>
using namespace std;

class BST {
    
    struct node {
        int data;
        node* left;
        node* right;
    };

    node* root;

    node* makeEmpty(node* t) {
        if(t == NULL)
            return NULL;
        {
            makeEmpty(t->left);
            makeEmpty(t->right);
            delete t;
        }
        return NULL;
    }

    node* insert(int x, node* t)
    {
        if(t == NULL)
        {
            t = new node;
            t->data = x;
            t->left = t->right = NULL;
        }
        else if(x < t->data)
            t->left = insert(x, t->left);
        else if(x > t->data)
            t->right = insert(x, t->right);
        return t;
    }

    node* findMin(node* t)
    {
        if(t == NULL)
            return NULL;
        else if(t->left == NULL)
            return t;
        else
            return findMin(t->left);
    }

    node* findMax(node* t) {
        if(t == NULL)
            return NULL;
        else if(t->right == NULL)
            return t;
        else
            return findMax(t->right);
    }

    void inorder(node* t) {
        if(t == NULL)
            return;
        inorder(t->left);
        cout << t->data << " ";
        inorder(t->right);
    }

    bool CheckIfBST(node* t, int min,  int max) {
    // Base case. An empty tree is a BST.
      if (t == NULL){
        cout << "here1" << endl;
        return true;
      }
      // Checking if a key is outside the permitted range.
      if (t -> data < min){
        cout << "here2" << endl;
        return false;
      }

      if (t -> data > max){
        cout << "here3" << endl;
        return false;
      }
      cout << "here4" << endl;
      // Sending in updates ranges to the right and left subtree
      return CheckIfBST(t -> right, t -> data, max) && CheckIfBST(t -> left, min, t -> data);				
    }

public:
    BST() {
        root = NULL;
    }

    ~BST() {
        root = makeEmpty(root);
    }

    void insert(int x) {
        root = insert(x, root);
    }

    void display() {
        inorder(root);
        cout << endl;
    }
    int getMin(){
      node* temp1;
      temp1 = findMin(root);
      return temp1->data;
    }

    int getMax(){
      node* temp;
      temp = findMax(root);
      return temp->data;
  }

  bool isBst(){
  int min = std::numeric_limits<int>::min();
  int max = std::numeric_limits<int>::max();
   bool results = CheckIfBST(root, min, max);
   cout << "This is results for CheckIfBST: " << results << endl;
   if(results == 1){
       cout << "Is BST";
     }else{
       cout << "Not a BST";
     }
   return results;
  }
};

int main() 
{ 
  BST t;
  string mystr;
  int tmp; // A string to store the word on each iteration.
  cout << "What are the numbers" << endl;
  getline (cin, mystr);

  stringstream str_strm(mystr);
  vector<int> myvect; 
  while (str_strm >> tmp) {
      myvect.push_back(tmp);
  }
  
  for(int i =0; i < myvect.size(); i++){
    t.insert(myvect[i]);
  }
   //t.isBst();
  //t.display();
  // cout << t.getMin() << endl;
  // cout << t.getMax() << endl;
  cout << t.isBst()  << endl;


	return 0;	 
} 

[salem c]

> cout << "here4" << endl;
When you get to here, also print
- min
- max
- t->data

Does it look like you're following a tree traversal?

> return CheckIfBST(t -> right, t -> data, max) && CheckIfBST(t -> left, min, t -> data);

It might be worth doing left then right, if only for sanity in your debug log
return CheckIfBST(t -> left, min, t -> data) && CheckIfBST(t -> right, t -> data, max);

[seeplus]

Couple of points

1) You should always initialize variables when defined

2) Use nullptr rather than NULL in C++ code

#include <iostream>
#include <string>
#include <limits>
#include <sstream>
#include <vector>

// C++ implementation to check if the given array
// can represent Level Order Traversal of Binary
// Search Tree

using namespace std;

#include <iostream>
using namespace std;

class BST {

	struct node {
		int data {};
		node* left {};
		node* right {};
	};

	node* root {};

	node* makeEmpty(node* t)
	{
		if (t != nullptr) {
			makeEmpty(t->left);
			makeEmpty(t->right);
			delete t;
		}

		return nullptr;
	}

	node* insert(int x, node* t)
	{
		if (t == nullptr) {
			t = new node {};
			t->data = x;
			t->left = t->right = nullptr;
		} else
			if (x < t->data)
				t->left = insert(x, t->left);
			else
				if (x > t->data)
					t->right = insert(x, t->right);

		return t;
	}

	node* findMin(node* t) const
	{
		if (t == nullptr || t->left == nullptr)
			return t;

		return findMin(t->left);
	}

	node* findMax(node* t) const
	{
		if (t == nullptr || t->right == nullptr)
			return t;

		return findMax(t->right);
	}

	void inorder(node* t) const
	{
		if (t != nullptr) {
			inorder(t->left);
			cout << t->data << " ";
			inorder(t->right);
		}
	}

	bool CheckIfBST(node* t, int min, int max) const
	{
		// Base case. An empty tree is a BST.
		if (t == nullptr) {
			cout << "here1" << endl;
			return true;
		}

		// Checking if a key is outside the permitted range.
		if (t->data < min) {
			cout << "here2" << endl;
			return false;
		}

		if (t->data > max) {
			cout << "here3" << endl;
			return false;
		}

		cout << "here4" << endl;
		// Sending in updates ranges to the right and left subtree
		return CheckIfBST(t->right, t->data, max) && CheckIfBST(t->left, min, t->data);
	}

public:
	BST() {}

	~BST()
	{
		root = makeEmpty(root);
	}

	void insert(int x)
	{
		root = insert(x, root);
	}

	void display() const
	{
		inorder(root);
		cout << endl;
	}

	int getMin() const
	{
		return findMin(root)->data;
	}

	int getMax() const
	{
		return findMax(root)->data;
	}

	bool isBst() const
	{
		constexpr int min {std::numeric_limits<int>::min()};
		constexpr int max {std::numeric_limits<int>::max()};
		const bool results {CheckIfBST(root, min, max)};

		cout << "This is results for CheckIfBST: " << results << endl;

		if (results == true)
			cout << "Is BST";
		else
			cout << "Not a BST";

		return results;
	}
};

int main()
{
	BST t;
	string mystr;
	int tmp; // A string to store the word on each iteration.

	cout << "What are the numbers" << endl;
	getline(cin, mystr);

	stringstream str_strm(mystr);
	vector<int> myvect;

	while (str_strm >> tmp) {
		myvect.push_back(tmp);
	}

	for (int i = 0; i < myvect.size(); i++) {
		t.insert(myvect[i]);
	}

	//t.isBst();
   //t.display();
   // cout << t.getMin() << endl;
   // cout << t.getMax() << endl;
	cout << t.isBst() << endl;

	return 0;
}