I have been scratching my head for a while on this C program debug. I'm trying to write a program to help validate if the binary search tree syntax is correct by construction. I'm not a lost for why my program seems to be crashing at the recursive part of the program.
Here is my full code:
#include <stdexcept>
#include <string>
#include <iostream>
#include <algorithm>
class Node
{
public:
Node(int value, Node* left, Node* right)
{
this->value = value;
this->left = left;
this->right = right;
}
int getValue() const
{
return value;
}
Node* getLeft() const
{
return left;
}
Node* getRight() const
{
return right;
}
private:
int value;
Node* left;
Node* right;
};
class BinarySearchTree
{
public:
static bool isValidBST(const Node* node) {
std::cout << "DEBUG 1\n";
/* false if left is > than node */
if (node->getLeft() != NULL && node->getLeft()->getValue() > node->getValue())
return false;
std::cout << "DEBUG 2\n";
/* false if right is < than node */
if (node->getRight() != NULL && node->getRight()->getValue() < node->getValue())
return false;
std::cout << "DEBUG 3\n";
/* false if, recursively, the left or right is not a BST */
//std::cout << isValidBST(node->getLeft()) << std::endl;
if (!isValidBST(node->getLeft()) || !isValidBST(node->getRight()))
return false;
/* passing all that, it's a BST */
return true;
}
};
#ifndef RunTests
int main()
{
Node n1(1, NULL, NULL);
Node n3(3, NULL, NULL);
Node n2(2, &n1, &n3);
std::cout << " TEST ";
std::cout << BinarySearchTree::isValidBST(&n2);
std::cout << " DONE " ;
return 0;
}
#endif```
CodePudding user response：
Your program suffers from too much repetition, and some assumptions about pointers. To begin with, if you call isValidBST(NULL) your program exhibits undefined behavior even though one expects that an empty tree is a valid BST.
Beyond this, your compound conditional statements are duplicating not only pointer test logic, but also the comparisons which it turns out you also did not get correct. You have not considered that duplicate values in a BST are also invalid, and so fixing this logic requires multiple edits.
In general, maintaining identical logic in multiple parts of a program (or a function) adds the potential for future bugs, and it's good to avoid when possible. This is especially true when the duplicated logic is inverted.
Consider the following rearrangement of your function, with the logic in one place:
class BinarySearchTree
{
public:
static bool isValidBST(const Node* node)
{
const Node* prev = NULL;
return isValidBST(node, prev);
}
private:
static bool isValidBST(const Node* node, const Node* &prev)
{
if (!node)
return true;
// Validate left
if (!isValidBST(node->getLeft(), prev))
return false;
// Validate current
if (prev && prev->getValue() >= node->getValue())
return false;
prev = node;
// Validate right
return isValidBST(node->getRight(), prev);
}
};
The function bootstraps a private overload that maintains a pointer of the last value node tested. In this way, you can see the code is vastly simplified and more obvious to the reader.
CodePudding user response：
You need to check that in isValidBST method your node variable is null or not. if node is null and you call
node->getLeft(), node->getRight() or node->getValue()
you will get an error. You need to add null check conditon in isValidBST method
if(node == NULL) return true;
Your can resolve this like
#include <stdexcept>
#include <string>
#include <iostream>
#include <algorithm>
class Node
{
public:
Node(int value, Node* left, Node* right)
{
this->value = value;
this->left = left;
this->right = right;
}
int getValue() const
{
return value;
}
Node* getLeft() const
{
return left;
}
Node* getRight() const
{
return right;
}
private:
int value;
Node* left;
Node* right;
};
class BinarySearchTree
{
public:
static bool isValidBST(const Node* node) {
if(node == NULL) return true;
std::cout << "DEBUG 1\n";
/* false if left is > than node */
if (node->getLeft() != NULL && node->getLeft()->getValue() > node->getValue())
return false;
std::cout << "DEBUG 2\n";
/* false if right is < than node */
if (node->getRight() != NULL && node->getRight()->getValue() < node->getValue())
return false;
std::cout << "DEBUG 3\n";
/* false if, recursively, the left or right is not a BST */
//std::cout << isValidBST(node->getLeft()) << std::endl;
if (!isValidBST(node->getLeft()) || !isValidBST(node->getRight()))
return false;
/* passing all that, it's a BST */
return true;
}
};
#ifndef RunTests
int main()
{
Node n1(1, NULL, NULL);
Node n3(3, NULL, NULL);
Node n2(2, &n1, &n3);
std::cout << " TEST ";
std::cout << BinarySearchTree::isValidBST(&n2);
std::cout << " DONE " ;
return 0;
}
#endif```
CodePudding user response：
I found a logic bug with my recursive program:
needed this extra case with the NULL left and NULL right node.
class BinarySearchTree
{
public:
static bool isValidBST(const Node* node) {
std::cout << "DEBUG 1\n";
/* false if left is > than node */
if (node->getLeft() != NULL && node->getLeft()->getValue() > node->getValue())
return false;
std::cout << "DEBUG 2\n";
/* false if right is < than node */
**if (node->getRight() != NULL && node->getRight()->getValue() < node->getValue())
return false;**
std::cout << "DEBUG 3\n";
if (node->getLeft() == NULL && node->getRight() == NULL) {
return true;
}
/* false if, recursively, the left or right is not a BST */
//std::cout << isValidBST(node->getLeft()) << std::endl;
if (!isValidBST(node->getLeft()) || !isValidBST(node->getRight()))
return false;
/* passing all that, it's a BST */
return true;
}
};```