Question

Implement a function to find a node in a binary search tree. Using the following class and function definition:

class BTNode {
public:
   int item;
   BTNode *left;
   BTNode *right;
   BTNode(int i, BTNode *l=nullptr, BTNode *r=nullptr):item(i),left(l),right(r){}
};

BTNode *root = nullptr;

BTNode* find(int i) {
     // implement
}

If a node with a matching value is found, return a pointer to it. If no match is found, return nullptr.

#include <iostream>

class BTNode {
public:
int item;
BTNode *left;
BTNode *right;
BTNode(int i, BTNode *l=nullptr, BTNode *r=nullptr):item(i),left(l),right(r){}
};

BTNode *root = nullptr;

BTNode *find(int item)
{
return nullptr;
}

int main()
{   
root = new BTNode(10, new BTNode(1), new BTNode(20));

BTNode *t1 = find(10);
if (t1)
std::cout << "Found " << t1->item << std::endl;
else
std::cout << "Should have found 10." << std::endl;

  
BTNode *t2 = find(1);
if (t1)
std::cout << "Found " << t2->item << std::endl;
else
std::cout << "Should have found 1." << std::endl;

BTNode *t3 = find(20);
if (t3)
std::cout << "Found " << t3->item << std::endl;
else
std::cout << "Should have found 20." << std::endl;

BTNode *t4 = find(100);
if (t4)
std::cout << "Should have found 20." << std::endl;   
else
std::cout << "Did not find 100." << std::endl;
  

return 0;
}

Answer 1

Solution

#include <iostream>

class BTNode {
public:
int item;
BTNode *left;
BTNode *right;
BTNode(int i, BTNode *l=nullptr, BTNode *r=nullptr):item(i),left(l),right(r){}
};

BTNode *root = nullptr;

BTNode *find(int item)
{
BTNode *temp = root;
while(temp != nullptr)
{
if(temp->item < item)
temp = temp->right;
else if(temp->item > item)
temp = temp->left;
else
return temp;
}
return nullptr;
}

int main()
{
root = new BTNode(10, new BTNode(1), new BTNode(20));
BTNode *t1 = find(10);
if (t1)
std::cout << "Found " << t1->item << std::endl;
else
std::cout << "Should have found 10." << std::endl;

BTNode *t2 = find(1);
if (t1)
std::cout << "Found " << t2->item << std::endl;
else
std::cout << "Should have found 1." << std::endl;

BTNode *t3 = find(20);
if (t3)
std::cout << "Found " << t3->item << std::endl;
else
std::cout << "Should have found 20." << std::endl;

BTNode *t4 = find(100);
if (t4)
std::cout << "Should have found 20." << std::endl;
else
std::cout << "Did not find 100." << std::endl;

return 0;
}

Output:

Solving your question and helping you to well understand it is my focus. So if you face any difficulties regarding this please let me know through the comments. I will try my best to assist you. However if you are satisfied with the answer please don't forget to give your feedback. Your feedback is very precious to us, so don't give negative feedback without showing proper reason.
Always avoid copying from existing answers to avoid plagiarism.
Thank you.