1. Introduction

The Binary Search Tree (BST) is a binary tree where each node has a value, and the nodes to the left have values less than the node, and the nodes to the right have values greater than the node. Searching for a key in a BST is an efficient operation as it reduces the problem size by half with each level (logarithmic time). In this blog post, we will implement a method to search for a given key in a BST.

2. Program Steps

1. Start from the root of the BST.

2. Compare the root’s value with the given key.

3. If the root’s value is equal to the key, return true.

4. If the root’s value is less than the key, search the right subtree.

5. If the root’s value is greater than the key, search the left subtree.

6. Repeat steps 2 to 5 for the subtree, treating the subtree root as the current root.

7. If the end of the BST is reached and the key has not been found, return false.

3. Code Program

public class SearchBST {

    static class Node {
        int data;
        Node left, right;

        Node(int item) {
            data = item;
            left = right = null;
        }
    }

    Node root;

    boolean search(Node root, int key) {
        // Base Case: root is null or key is present at root
        if (root == null || root.data == key) {
            return root != null;
        }

        // If key is greater than root's key, recur for right subtree
        if (root.data < key) {
            return search(root.right, key);
        }

        // If key is smaller than root&apos;s key, recur for left subtree
        return search(root.left, key);
    }

    public static void main(String[] args) {
        SearchBST tree = new SearchBST();
        Node root = new Node(50);
        tree.root = root;
        tree.root.left = new Node(30);
        tree.root.left.left = new Node(20);
        tree.root.left.right = new Node(40);
        tree.root.right = new Node(70);
        tree.root.right.left = new Node(60);
        tree.root.right.right = new Node(80);

        int key = 65;
        if (tree.search(root, key)) {
            System.out.println("Key " + key + " found in BST");
        } else {
            System.out.println("Key " + key + " not found in BST");
        }
    }
}

Output:

Key 65 not found in BST

4. Step By Step Explanation

1. We start by defining a Node class representing each node in the BST.

2. The BST is represented by the SearchBST class which has a search function.

3. The search function uses recursion to traverse through the BST. It compares the current node's data with the key and based on that, decides whether to search in the left subtree or the right subtree.

4. If the key matches any node's data during traversal, the function returns true. If the end of the BST is reached without finding the key, it returns false.

5. In the main function, a BST is created and the search function is invoked with a specific key (65 in this case). The output displays whether the key was found in the BST or not.