Problem Statement:
Given a BST and a key element, you need to find if the key element is present in BST or not.
Solution
The solution is very simple.
We take the key element and compare with the root, if the key element is smaller then we go to the left sub tree else we go to the right sub tree.
We continue this process till we find a value or till we reach a leaf node.
Solution in C++
#include <algorithm>
//visit www.ProDeveloperTutorial.com for 450+ solved questions
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <stack>
#include <unordered_map>
using namespace std;
struct Node
{
int data;
Node *left;
Node *right;
};
//global root declaration
Node *root;
Node* insert(int num, Node* root)
{
if(root == NULL)
{
root = new Node;
root->data = num;
root->left = root->right = NULL;
}
else if(num < root->data)
root->left = insert(num, root->left);
else if(num > root->data)
root->right = insert(num, root->right);
return root;
}
void inorder(Node *root)
{
if(root == NULL)
return;
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
Node* find(Node *root, int key)
{
if(root == NULL)
return NULL;
else if(key < root->data)
return find(root->left, key);
else if(key > root->data)
return find(root->right, key);
else
return root;
}
int main()
{
root = insert(10, root);
root = insert(30, root);
root = insert(20, root);
root = insert(50, root);
root = insert(60, root);
root = insert(25, root);
root = insert(15, root);
int key = 60;
if(find(root, key) != NULL)
cout<<"\nThe key "<<key<<" is present\n"<<endl;
else
cout<<"\nThe key "<<key<<" is not present\n"<<endl;
return 0;
}
Output:
The key 60 is present