Search given Key in BST

Dec 18, 2024 • 3 mins read

Problem Overview

The problem requires us to search for a specific value in a Binary Search Tree (BST). We're given the root of a BST and a value to search for. Our task is to return the subtree whose root node matches the search value. If no such node exists, we should return null.

Example:

Consider a BST:

If the target value is 2, the subtree rooted at 2 is returned:

    2
   / \
  1   3

If the target value is 5, the function should return null as 5 is not in the BST.

Understanding the Problem

In simpler words, the problem is about traversing a Binary Search Tree to find a node with the specified value. The given BST property allows us to reduce the number of nodes we need to visit, as for any node n, values in its left subtree are less than n.value and values in its right subtree are greater than n.value.

Constraints:

The number of nodes in the tree will be in the range of [1, 5000].
0 <= Node.val <= 10^7
The value of nodes in the BST are unique.
0 <= target <= 10^7

Key DSA Concepts and Theory

Binary Search Tree

A Binary Search Tree (BST) is a node-based binary tree data structure which has the following properties:

The left subtree of a node contains only nodes with values less than the node’s value.
The right subtree of a node contains only nodes with values greater than the node’s value.
Both the left and right subtrees must also be binary search trees.

The BST property helps in efficient searching, insertion, and deletion operations.

Depth-First Search (DFS)

For this problem, a common approach to traverse a tree is Depth-First Search (DFS). DFS can be implemented using recursion, visiting all the nodes by following each branch as far as possible.

Recursion

Recursion is a method where the solution to a problem depends on solutions to smaller instances of the same problem. In the case of trees, recursion fits naturally as each tree is itself a recursive structure.

Solution Approach

The solution primarily utilizes the BST property to efficiently locate the target node. We aim to minimize the nodes traversed by each time only visiting potentially viable subtrees.

Detailed Steps

Base Case: If the current node is null, return null indicating the target is not found in this path.
Check Current Node: Compare the node's value with the target value:
- If they are equal, return the current node as we found the target.
- If the target is smaller, search in the left subtree (node.left).
- If the target is greater, search in the right subtree (node.right).

C++ Code Implementation

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr || root->val == val) {
            return root;
        }
        
        if (val < root->val) {
            return searchBST(root->left, val);
        } else {
            return searchBST(root->right, val);
        }
    }
};

Java Code Implementation

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    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);
        }
    }
}

Time and Space Complexity Analysis

Time Complexity: O(h), where h is the height of the tree. In the worst case scenario for a skewed tree (like a linked list), the height could be O(n), where n is the number of nodes.
Space Complexity: O(h) due to the recursion stack. This is needed to store the function calls until we reach the target.

Common Mistakes to Avoid

Incorrect Base Case: Ensure that you check if the current node is null or matches the value before progressing the search.
Misusing BST Property: Traversal logic needs to strictly observe the BST properties for efficient searching. Checking the wrong subtree can lead to incorrect results.