Binary Search Trees: Given a BST and a key, search in a BST

Problem Statement:

Given a BST and a key, search in a BST

Example:

Input:

    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */

key = 12

Output:

True

Solution Explanation:

Traverse the BST starting from root and then check if the value is equal to the key and then return true or false accordingly.

Time Complexity: O(h)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class Tree_Node 
{
public:
	int data;
	Tree_Node* left;
	Tree_Node* right;

	Tree_Node(int x) 
	{
		data = x;
		left = nullptr;
		right = nullptr;
	}
};

bool solution(Tree_Node* root, int key) 
{
    
    Tree_Node* curr = root;
    
    while (curr != nullptr) 
    {
        
        if (curr->data == key)
            return true;
            
        else if (curr->data < key) 
            curr = curr->right;
            
        else
            curr = curr->left;
    }
    
    return false;
}

int main()
{

    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */
    Tree_Node* root = new Tree_Node(10);
    root->left = new Tree_Node(8);
    root->right = new Tree_Node(12);
    root->left->left = new Tree_Node(2);
    root->left->right = new Tree_Node(9);
    root->right->left = new Tree_Node(11);
    root->right->right = new Tree_Node(14);

    int key = 12;

    cout <<solution(root, key);

    return 0;
}

Output

1