logo CodeStepByStep logo

Main Page → Exercises → C++ → Solve an Exercise

bstContains

Language/Type: C++ binary trees pointers recursion

Write a function named bstContains that accepts a pointer to a BinaryTreeNode representing the root of a binary search tree of integers, along with an integer value. Your function should search the BST and return true if the given element value is found in the tree, and false if not. You may assume that the tree passed is in BST order, meaning that every node N's left subtree is a BST that contains only values less than N's data, and its right subtree is a BST that contains only values greater than N's data. Your code should perform a proper binary search and should not examine any subtrees where there is no possibility for the element value to be present.

Constraints: You must implement your function recursively and without using loops. Do not construct any new BinaryTreeNode objects in solving this problem (though you may create as many BinaryTreeNode* pointer variables as you like). Do not use any auxiliary data structures to solve this problem (no array, vector, stack, queue, string, etc). Your function should not modify the tree's state; the state of the tree should remain constant with respect to your function.

Assume that you are using the BinaryTreeNode structure as defined below: 

struct BinaryTreeNode {
    int data;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
};
Function: Write a C++ function as described, not a complete program.

You must log in before you can solve this problem.

Log In

Need help?

Stuck on an exercise? Contact your TA or instructor.

If something seems wrong with our site, please

Is there a problem? Contact us.