Skip to content
Shadow Cipher

BST Search

#include <bits/stdc++.h> // Includes common standard libraries (iostream)


using namespace std;     // Use the standard namespace


// Definition of a Node in the Binary Search Tree
class Node {
public:
    int data;     // Data value of the node
    Node* left;   // Pointer to the left child
    Node* right;  // Pointer to the right child


    // Constructor to initialize a new node
    Node(int data) {
        this->data = data;
        this->left = NULL;  // Initially, left child is NULL
        this->right = NULL; // Initially, right child is NULL
    }
};


// Function to insert a new node with 'data' into the BST
// (Standard BST insertion, used to build the tree for searching)
Node* insertIntoBST(Node* root, int data) {
    if(root == NULL) {
        root = new Node(data);
        return root;
    }


    if(data > root->data) {
        root->right = insertIntoBST(root->right, data);
    } else { // Handles duplicates by placing them on the left
        root->left = insertIntoBST(root->left, data);
    }


    return root;
}


// Function to take input from the user and build the BST
void takeinput(Node* &root) {
    int data;
    cout << "Enter data for node (enter -1 to stop): ";
    cin >> data;


    while(data != -1) {
        root = insertIntoBST(root, data);
        cout << "Enter data for node (enter -1 to stop): ";
        cin >> data;
    }
}


// Function to search for a 'key' in the Binary Search Tree recursively.
// Time Complexity: O(H) where H is the height of the tree.
// Space Complexity: O(H) due to recursion stack.
bool SearchBST(Node* root, int key) {
    // Base Case 1: If the current node is NULL, the key is not found in this path.
    if(root == NULL) {
        return false;
    }


    // Base Case 2: If the current node's data matches the key, we found it!
    if(root->data == key) {
        return true;
    }


    // Recursive Step: Decide whether to go right or left based on BST property
    if(key > root->data) {
        // If key is greater than current node's data, search in the right subtree.
        return SearchBST(root->right, key);
    } else { // key < root->data
        // If key is smaller than current node's data, search in the left subtree.
        return SearchBST(root->left, key);
    }
}


int main() {
    Node* root = NULL; // Initialize the root of the BST to NULL


    // Build the BST by taking input from the user
    cout << "--- Creating Binary Search Tree ---" << endl;
    takeinput(root);
    cout << endl;


    int key;
    cout << "Enter the key to search: ";
    cin >> key; // Get the key to search from the user


    // Perform the search operation
    bool found = SearchBST(root, key);


    // Print the result of the search
    if(found) {
        cout << "Key " << key << " is present in BST!" << endl;
    } else {
        cout << "Key " << key << " is absent in BST!" << endl;
    }


    return 0; // End of the program
}


/*
Example INPUT for tree creation:
50 20 70 10 30 60 80 -1


Expected Tree Structure:
        50
       /  \
      20  70
     / \  / \
    10 30 60 80


Example Searches:
1. Search Key: 30
   Output: Key 30 is present in BST!
2. Search Key: 90
   Output: Key 90 is absent in BST!
*/

1. Binary Search Tree (BST) Recap

  • A Binary Search Tree (BST) is a hierarchical data structure where for every node:
    • All values in its left subtree are less than the node’s data.
    • All values in its right subtree are greater than the node’s data.
    • Both left and right subtrees are also BSTs.
  • This ordering property is what makes searching efficient.

2. Node Class

  • The basic building block of the BST, containing data, left (child pointer), and right (child pointer).

3. insertIntoBST and takeinput (Briefly)

  • insertIntoBST: A recursive function to add new data into the BST while maintaining its properties.
  • takeinput: A utility function that reads integer input from the user (-1 to stop) to build the BST that will be searched.

  • Purpose: To determine if a specific key value exists within the BST.

  • Core Idea: The search process is highly efficient because, at each node, the BST property allows us to eliminate one half of the remaining tree (either the left or right subtree), similar to a binary search on a sorted array.

  • Logic:

    1. Base Case 1 (Key Not Found):
      • If root is NULL, it means we have traversed down an empty path or reached beyond a leaf node without finding the key. The key is not present in the tree. Return false.
    2. Base Case 2 (Key Found):
      • If root->data is equal to the key, we have found the target node. Return true.
    3. Recursive Step:
      • If key is greater than root->data:
        • According to BST properties, if the key exists, it must be in the right subtree. So, recursively call SearchBST on root->right.
      • If key is less than root->data:
        • The key must be in the left subtree. So, recursively call SearchBST on root->left.

  • Return Value: Returns true if the key is found anywhere in the subtree rooted at root, false otherwise.

  • Time Complexity: O(H)
    • H is the height of the BST. In each step, the search effectively moves down one level of the tree.
    • Best Case (Balanced BST): H = log N. So, O(log N). This is highly efficient.
    • Worst Case (Skewed BST/Linear Chain): H = N. So, O(N). This degenerates to linear search performance.
  • Space Complexity: O(H)
    • Due to the recursion call stack.