Binary Search Tree Contains Function
- by Suede
I am trying to write a "contains" function for a binary search tree. I receive the following error at compile "Unhandled exception at 0x77291CB3 (ntdll.dll) in BST.exe: 0xC00000FD: Stack overflow (parameters: 0x00000001, 0x001E2FFC)." The following is my code.
struct Node {
int data;
Node* leftChild;
Node* rightChild;
Node() : leftChild(NULL), rightChild(NULL) {}
};
struct BST {
Node* root;
BST() : root(NULL) {}
void insert(int value);
bool contains(int value);
};
void BST::insert(int value) {
Node* temp = new Node();
temp->data = value;
if(root == NULL) {
root = temp;
return;
}
Node* current;
current = root;
Node* parent;
parent = root;
current = (temp->data < current->data ? (current->leftChild) : (current->rightChild)
while(current != NULL) {
parent = current;
current = (temp->data < current->data) ? (current->leftChild) : (current->rightChild)
}
if(temp->data < parent->data) {
parent->leftChild = temp;
}
if(temp->data > parent->data) {
parent->rightChild = temp;
}
}
bool BST::contains(int value) {
Node* temp = new Node();
temp->data = value;
Node* current;
current = root;
if(temp->data == current->data) { // base case for when node with value is found
std::cout << "true" << std::endl;
return true;
}
if(current == NULL) { // base case if BST is empty or if a leaf is reached before value is found
std::cout << "false" << std::endl;
return false;
}
else { // recursive step
current = (temp->data < current->data) ? (current->leftChild) : (current->rightChild);
return contains(temp->data);
}
}
int main() {
BST bst;
bst.insert(5);
bst.contains(4);
system("pause");
}
As it stands, I would insert a single node with value '5' and I would search the binary search tree for a node with value '4' - thus, I would expect the result to be false.
