Binary Search Tree Contains Function

Question

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.

Answer 1

current is a local variable in the contains() function. When the function is called recursively, each new call will get it's own set of local variables an won't see what an outer call did to the local variables in the outer function.

Especially, before the recursive call, the function sets the current node to a node that should be searched next. But the called function will never see that current variable, it will get its own current variable, initialize it to root, and start searching from there.

Each recursive call will start searching from the beginning and then call itself again, until you run out of stack memory and get a stack overflow.

Instead of setting the current variable you should pass the current node as an additional parameter to the recursive call of the contains() function.

If you don't want to change the parameters of contains() the good way to handle this would probably be to move the real work to a helper function that takes deals with the additional parameter:

bool BST::contains(int value) {
   return contains_rec(value, root);
}

bool BST::contains_rec(int value, Node *current) {
   ...
}

If you make the helper function private you can also make sure nobody gets confused by it's presence or calls it by accident.

Another possibility would be to avoid recursion altogether and use a loop instead.