Search in a Binary Search Tree

In this post, we will discuss how to search for a specific value in a Binary Search Tree (BST). A BST is a special kind of binary tree where each node has a value greater than all values in its left subtree and less than all values in its right subtree.

Problem Definition

Given a binary search tree and a target value, the goal is to determine if the target value exists in the tree. If it exists, we return the corresponding node; otherwise, we return NULL.

Approach

To search for a value in a BST, we can utilize the properties of the BST. Starting from the root node, we compare the target value with the value of the current node:

1. If the target value is equal to the current node's value, we have found the target, and we return the current node.
2. If the target value is less than the current node's value, we search in the left subtree.
3. If the target value is greater than the current node's value, we search in the right subtree.

Steps:

1. Start from the root node.
2. If the current node is NULL, return NULL.
3. Compare the target value with the current node's value:
   • If they are equal, return the current node.
   • If the target value is less, move to the left child.
   • If the target value is greater, move to the right child.
4. Repeat until you find the target or exhaust the tree.

C++ Code Implementation

#include <iostream>
using namespace std;

// Definition for a binary search tree node
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// Function to search a value in a binary search tree
TreeNode* searchBST(TreeNode* root, int val) {
    if (root == NULL || root->val == val) {
        return root;
    }
    if (val < root->val) {
        return searchBST(root->left, val);
    } else {
        return searchBST(root->right, val);
    }
}

int main() {
    TreeNode* root = new TreeNode(4);
    root->left = new TreeNode(2);
    root->right = new TreeNode(7);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(3);

    int target = 2;
    TreeNode* result = searchBST(root, target);

    if (result != NULL) {
        cout << "Found: " << result->val << endl;
    } else {
        cout << "Value not found in the BST." << endl;
    }

    return 0;
}

JAVA Code Implementation

// Definition for a binary search tree node
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    // Constructor for initializing a TreeNode with a value
    TreeNode(int x) {
        val = x;
        left = null;
        right = null;
    }
}

public class BinarySearchTree {

    // Function to search a value in a binary search tree
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        if (val < root.val) {
            return searchBST(root.left, val);
        } else {
            return searchBST(root.right, val);
        }
    }

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

        // Building the binary search tree
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);

        // Define the target value to search for
        int target = 2;
        
        // Search for the target value in the tree
        TreeNode result = bst.searchBST(root, target);

        // Output the result
        if (result != null) {
            System.out.println("Found: " + result.val);
        } else {
            System.out.println("Value not found in the BST.");
        }
    }
}

Time and Space Complexity

Time Complexity

• Best Case: $O(\log n)$ - When the tree is balanced, each comparison halves the search space.
• Average Case: $O(\log n)$ - For a reasonably balanced BST.
• Worst Case: $O(n)$ - When the tree is completely skewed (all nodes on one side), resembling a linked list.

Space Complexity

• $O(\log n)$ - For the recursion stack in a balanced tree.
• $O(n)$ - In the worst case for a skewed tree.

Explanation

BST search leverages the ordering property where the left subtree contains smaller values and the right subtree contains larger values. Starting from the root, each comparison eliminates half the remaining nodes in a balanced tree. This efficient pruning makes BST search logarithmic on average. However, the search degrades to linear time in a skewed tree. Self-balancing trees (AVL, Red-Black) maintain logarithmic search time regardless of insertion order.