1. Objective

Given a value, determine whether it exists in a Binary Search Tree (BST).
The search operation leverages the inherent sorted structure of a BST to perform an efficient lookup.

2. Binary Search Tree Property Recap

In a BST:

• All values in the left subtree of a node are less than the node’s value.
• All values in the right subtree are greater than the node’s value.

This structure allows for binary search, which reduces the search space by half with each comparison.

3. Real-World Analogy

Imagine looking for a word in a dictionary:

• You don’t check every page sequentially.
• Instead, you open near the middle, check the word, and go left or right.
• That’s how BST search works — narrowing down based on comparison.

4. Visual Example

Let’s take the following BST:

        50
       /  \
     30    70
    / \    / \
  20  40  60 80

Searching for 60:

• 60 > 50 → move right
• 60 < 70 → move left
• 60 == 60 → Found

Searching for 25:

• 25 < 50 → move left
• 25 < 30 → move left
• 25 > 20 → move right (null)
• Not found

5. Steps to Search a Value in BST

1. Start at the root.
2. If the current node is null, the value is not found.
3. If the current node’s value == search value, return true.
4. If the search value < current node, go left.
5. If the search value > current node, go right.
6. Repeat the process until you find the value or reach a null node.

6. Java Implementation

Step 1: Tree Node Class

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    public TreeNode(int value) {
        this.data = value;
        this.left = null;
        this.right = null;
    }
}

Step 2: Recursive Search

public class BinarySearchTree {
    TreeNode root;

    public BinarySearchTree() {
        this.root = null;
    }

    // Insert method for testing
    public void insert(int value) {
        root = insertRecursive(root, value);
    }

    private TreeNode insertRecursive(TreeNode node, int value) {
        if (node == null) return new TreeNode(value);

        if (value < node.data) node.left = insertRecursive(node.left, value);
        else if (value > node.data) node.right = insertRecursive(node.right, value);

        return node;
    }

    // Recursive Search Method
    public boolean search(int value) {
        return searchRecursive(root, value);
    }

    private boolean searchRecursive(TreeNode node, int value) {
        if (node == null) {
            return false; // Not found
        }

        if (node.data == value) {
            return true;  // Found
        }

        if (value < node.data) {
            return searchRecursive(node.left, value);
        } else {
            return searchRecursive(node.right, value);
        }
    }
}

Step 3: Iterative Search (Alternative)

public boolean searchIterative(int value) {
    TreeNode current = root;

    while (current != null) {
        if (current.data == value) {
            return true;
        } else if (value < current.data) {
            current = current.left;
        } else {
            current = current.right;
        }
    }

    return false;
}

Step 4: Testing the Search

public class SearchInBSTDemo {
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();

        int[] values = {50, 30, 70, 20, 40, 60, 80};
        for (int val : values) {
            bst.insert(val);
        }

        // Search for existing and non-existing values
        System.out.println("Search 60: " + bst.search(60)); // true
        System.out.println("Search 25: " + bst.search(25)); // false
        System.out.println("Search 80: " + bst.searchIterative(80)); // true
        System.out.println("Search 10: " + bst.searchIterative(10)); // false
    }
}