Binary Search Tree Contains Function

Posted by Suede on Stack Overflow See other posts from Stack Overflow or by Suede
Published on 2013-10-24T21:29:52Z Indexed on 2013/10/25 15:54 UTC
Read the original article Hit count: 140

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.

© Stack Overflow or respective owner

Related posts about c++

Related posts about exception