Lecture 296:- Searching in a Binary Search Tree

Searching in a Binary Search Tree (BST) is a fundamental operation that takes advantage of the ordering property of the tree. Since a BST is organized such that all nodes in the left subtree have keys less than the current node's key, and all nodes in the right subtree have keys greater than the current node's key, searching can be performed efficiently.

The searching algorithm in a BST can be implemented recursively or iteratively. Here's how you can perform a search for a key in a BST:

1. Recursive Approach:
   • Start at the root of the BST.
   • If the root is null or its key matches the target key, return the root (or indicate that the key is found).
   • If the target key is less than the root's key, search in the left subtree.
   • If the target key is greater than the root's key, search in the right subtree.
2. Iterative Approach:
   • Start at the root of the BST and initialize a pointer to track the current node.
   • While the current node is not null:
     • If the current node's key matches the target key, return the current node (or indicate that the key is found).
     • If the target key is less than the current node's key, move to the left child.
     • If the target key is greater than the current node's key, move to the right child.

Here's the C++ implementation of both recursive and iterative approaches for searching in a BST:

cppCopy code

#include <iostream> using namespace std; struct TreeNode {    int val;    TreeNode* left;    TreeNode* right;    TreeNode(int data) : val(data), left(nullptr), right(nullptr) {} }; // Recursive search in BST TreeNode* searchBSTRecursive(TreeNode* root, int target) {    if (root == nullptr || root->val == target)        return root;    if (target < root->val)        return searchBSTRecursive(root->left, target);    else        return searchBSTRecursive(root->right, target); } // Iterative search in BST TreeNode* searchBSTIterative(TreeNode* root, int target) {    while (root != nullptr && root->val != target) {        if (target < root->val)            root = root->left;        else            root = root->right;    }    return root; } int main() {    // Create a binary search tree:    //        5    //       / \    //      3   8    //     / \ / \    //    2  4 7  9    TreeNode* root = new TreeNode(5);    root->left = new TreeNode(3);    root->right = new TreeNode(8);    root->left->left = new TreeNode(2);    root->left->right = new TreeNode(4);    root->right->left = new TreeNode(7);    root->right->right = new TreeNode(9);    int target = 4;    // Recursive search    TreeNode* resultRecursive = searchBSTRecursive(root, target);    if (resultRecursive)        cout << "Recursive Search: Key " << target << " found." << endl;    else        cout << "Recursive Search: Key " << target << " not found." << endl;    // Iterative search    TreeNode* resultIterative = searchBSTIterative(root, target);    if (resultIterative)        cout << "Iterative Search: Key " << target << " found." << endl;    else        cout << "Iterative Search: Key " << target << " not found." << endl;    // Remember to free the allocated memory after use to avoid memory leaks.    delete root->left->left;    delete root->left->right;    delete root->left;    delete root->right->left;    delete root->right->right;    delete root->right;    delete root;    return 0; }

Output:

sqlCopy code

Recursive Search: Key 4 found. Iterative Search: Key 4 found.

In this example, we search for the key 4 in the given BST and find that it exists in both the recursive and iterative searches.