Search in a Binary Search Tree

Problem Description

You are 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 such a node does not exist, return null.

Key Insights

• A Binary Search Tree (BST) is structured such that for any given node, the left subtree contains values less than the node's value, and the right subtree contains values greater than the node's value.
• This property can be utilized to efficiently search for a value in the tree, allowing us to skip half of the tree at each step.
• The search operation has a time complexity of O(h), where h is the height of the tree, making it efficient even for larger trees.

Space and Time Complexity

Time Complexity: O(h)
Space Complexity: O(1) (iterative solution) or O(h) (recursive solution due to call stack)

Solution

To solve the problem, we can employ a recursive or iterative approach leveraging the properties of a BST. Starting from the root, we compare the target value (val) with the current node's value:

1. If the current node's value equals val, we return the current node.
2. If val is less than the current node's value, we recursively search in the left subtree.
3. If val is greater than the current node's value, we recursively search in the right subtree.
4. If we reach a null node, it means the value does not exist in the tree, and we return null.

This approach ensures that we efficiently navigate through the tree based on the value comparisons.

Code Solutions