Search in a Binary Search Tree

LeetCode Problem #700 (Easy)

Problem Statement

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node's value equals the given value. Return the subtree rooted with that node. If such node doesn't exist, you should return NULL.

Testcases

Example 1:

Input:
        4
       / \
      2   7
     / \
    1   3
    
Value to Search: 2
Output:
      2     
     / \   
    1   3

Example 2:

Input:
        4
       / \
      2   7
     / \
    1   3
    
Value to Search: 5
Output: []

Prerequisite Knowledge

Binary Search Tree

A binary search tree allows us to maintain a sorted list of elements in a tree-like data structure. Each node has a maximum of two children and the arrangement of nodes must follow three conditions:

1. All nodes to the left of a node must be less than that node.

2. All nodes to the right of a node must be greater than that node.

3. Every sub-tree of the binary search tree must also satisfy the properties listed above.

Searching in a BST

When an element must be searched in a binary search tree, we follow a procedure similar to that of binary search, wherein, with each iteration, we reduce the search space by half.

The current node value is compared with the value of the search key and the next search space is determined.

If the key is less than the node value, then the key is most likely located in the left sub-tree according to the BST rule.

If the search key is greater than the node value, then the key is most likely located in the right sub-tree according to the BST rule.

Source: https://www.programiz.com/dsa/binary-search-tree

Since the search space is reduced by half in every iteration, a binary search tree only takes O(logn) time to search for an element.

Algorithm

Recursive Approach

1. If the value at the current node being traversed is equal to the given value, then return the reference to that node.

2. If the value is less than the value of the current node, then it can only be found in the left sub-tree of the BST, so recursively call the function such that it traverses to the left of the current node.

3. If the value is greater than the value of the current node, then it can only be found in the right sub-tree of the BST, so recursively call the function such that it traverses to the right of the current node.

4. If the value to be searched is not found, return NULL.

Time Complexity: O(n)

Code

TreeNode* searchBST(TreeNode* root, int val) {
    if(root) {
        // Check if the value at the current node is equal to the given value
        if(root->val == val) {
        return root;
        }
        // Check left sub-tree
        else if(val < root->val) {
            return searchBST(root->left, val);
        }
        // Check right sub-tree
        else {
            return searchBST(root->right, val);
        }
    }
    return NULL;
}