Problem Statement

Given the root of a binary search tree (BST) and an integer val. Find the node in the BST that the node's value equals val and return the subtree rooted with that node.  If no such a node exists, return null.

Examples

Example 1:

Input:
Tree:
        4
       / \
      2   7
     / \
    1   3

val = 2

Output:
      2
     / \
    1   3


Explanation: The node with value 2 is found in the BST, and the subtree rooted at this node is returned.

Example 2:

Input:
Tree:
        4
       / \
      2   7
     / \
    1   3

val = 5

Output: null

Different Approaches

1️⃣ Iterative Approach

Intuition:

In a Binary Search Tree (BST), the key property is that for any given node N, all nodes in its left subtree contain values smaller than N, while all nodes in its right subtree hold values greater than N. This structure facilitates an efficient search for a value X, which can be understood through three distinct scenarios:

1. If the value at node N matches X, then N is the target node.

2. If the value at node N is less than X, the search must proceed to the right subtree, as X cannot exist in the left subtree.

3. If the value at node N is greater than X, the search must continue in the left subtree, since X cannot be found in the right subtree.

Approach:

1. Initiate a traversal of the tree using a while loop, conditioned on the root being non-NULL and the root's data not matching X.
2. If the root's data is less than X, shift the focus to the right child of the root.
3. If the root's data exceeds X, redirect the search to the left child of the root.
4. Upon exiting the loop, if the root is NULL, it indicates that X is not present in the tree, and the function should return NULL. Otherwise, return the node containing the value X.

Code:

//  Definition for a binary tree node.
struct TreeNode {
      int data;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
  };
 
class Solution {	
public:	
    TreeNode* searchBST(TreeNode* root, int val) {
        // Traverse the tree until we find the node 
        // with the given value or reach the end
        while (root != nullptr && root->data != val) {
            // Move to the left or right child 
           // depending on the value comparison
            root = (root->data > val) ? root->left : root->right;
        }
        // Return the found node or nullptr if not found
        return root; 
    }
};

// Example usage
int main() {
    // Creating a simple BST for demonstration
    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);

    Solution sol;
    TreeNode* result = sol.searchBST(root, 2);
    if (result) {
        std::cout << "Node found with value: " << result->data << std::endl;
    } else {
        std::cout << "Node not found" << std::endl;
    }

    // Clean up memory (omitted for brevity)
    return 0;
}

Complexity Analysis:

• Time Complexity: O(log2(N)): The time complexity is O(log2(N)) in a balanced BST since the search space is halved at each step. However, in the worst case (skewed tree), it can be O(N).
• Space Complexity: O(1): The space complexity is O(1) as the search is performed iteratively without using additional space.

2️⃣ Recursive Approach

Intuition:

The recursive approach uses the BST property to navigate the tree:

• If the value of the current node matches val, return the current node.
• If val is smaller, search in the left subtree.
• If val is larger, search in the right subtree.

Approach:

1. Start at the root.
2. If the root is nullptr, return nullptr.
3. Compare val with the root's value:
   • If equal, return the root.
   • If less, recursively search in the left subtree.
   • If greater, recursively search in the right subtree.

Code:

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        // Base case: root is nullptr or root's value matches val
        if (!root || root->data == val) {
            return root;
        }
        
        // Recursive search in the left or right subtree
        if (val < root->data) {
            return searchBST(root->left, val);
        } else {
            return searchBST(root->right, val);
        }
    }
};

Complexity Analysis:

• Time Complexity: O(h), where h is the height of the BST.
  • In the worst case (unbalanced tree), h=N.
  • In the best case (balanced tree), h=logN.
• Space Complexity: O(h) due to the recursive call stack.