Searching In A Binary Search Tree In C++

January 24, 2021

Searching In A Binary Search Tree

A binary search tree is a tree in which the data in left subtree is less than the root and the data in right subtree is greater than the root.Given a Binary Search tree and a key, check whether the key is present in the tree or not.

C++ Program To Search in BST

Algorithm Using Level Order Traversal:

  1. Initialize the queue.
  2. Add root to the queue.
  3. Until the queue is empty, add the left child and the right child of the current node.
  4. Pop the node.
  5. Traverse the queue, check whether key is equal to the value of node.
  6. If found return true otherwise false.

 

Searching a node in a Binary search tree in C++ using level order searching

Algorithm Using Recursion:

  1. If tree is empty return.
  2. Check whether key is greater or smaller than root.
  3. If greater, move to the right subtree. Otherwise move to the left subtree.
  4. If Key is found return true.
C++ Program To search in a BST using recursion

Code (Using Level Order):

#include<bits/stdc++.h> 
using namespace std; 
class Tree {
    public:
        int data;
        Tree* left = NULL,*right = NULL;
        // Constructor initialised
        Tree(int x) {
            data = x;
            left = NULL;
            right = NULL;
        }
};
// To check whether equal or not
bool check(int key,int element) {
    if (key == element) return true;
    return false;
}
void level_order(Tree *root, int key) {
    if (root == NULL) return;
    queue<Tree *> q, lev;
    q.push(root);
    // Getting Level Order
    while (!q.empty()) {
        Tree * temp = q.front();
        lev.push(temp);
        // Adding left child
        if (temp -> left != NULL) {
            q.push(temp -> left);
        }
        // Adding Right child
        if (temp -> right != NULL) {
            q.push(temp -> right);
        }
        q.pop();
    }
    bool ok = false;
    while (!lev.empty()) {
        if (check(lev.front() -> data,key)) {
            cout << “Found\n“;
            ok = true;
        }
        lev.pop();
    }
    // If not found
    if (!ok) {
        cout <<“Not Found”;
    }
}
int main() {
    Tree *root = new Tree(80);
    root -> left = new Tree(60);
    root -> right = new Tree(90);
    root -> left -> left = new Tree(40);
    root -> left -> right = new Tree(70);
    root -> left -> left -> left = new Tree(30);
    root -> left -> left -> right = new Tree(50);
    level_order(root,55); 
    return 0;
}

Output:

Not Found

Code (Recursion):

#include<bits/stdc++.h> 
using namespace std; 
class Tree {
    public:
        int data;
        Tree* left = NULL,*right = NULL;
        // Constructor initialised
        Tree(int x) {
            data = x;
            left = NULL;
            right = NULL;
        }
};
// To check whether equal or not
bool check_element(Tree * root, int key) {
    // If root is null, element is not found:Backtrack 
    if (root == NULL) {
        return false;
    }
    // Check whether same or not
    if (root -> data == key) {
        return true;
    }
    
    if (root -> data > key) {
        // Traverse the left subtree
        return check_element(root -> left, key);
    }
    // Else Traverse the right subtree
    else {
        return check_element(root -> right, key);
    }
}
int main() {
    Tree *root = new Tree(80);
    root -> left = new Tree(60);
    root -> right = new Tree(90);
    root -> left -> left = new Tree(40);
    root -> left -> right = new Tree(70);
    root -> left -> left -> left = new Tree(30);
    root -> left -> left -> right = new Tree(50);
    if (check_element(root,50)) {
        cout << “Found\n“;
    }
    else {
        cout << “Not Found\n“;
    }
    return 0;
}
 

Output:

Found

Time Complexity For Searching Element In A Binary Search Tree

Time Complexity

O(n) Queue and Recursion

Space Complexity

O(1) Queue and Recursion