algoadvance

You’re given the root of a binary search tree (BST) and an integer val. You need to write a function that searches the BST for the node whose value equals val and returns the subtree rooted with that node. If such a node doesn’t exist, return null.

Clarifying Questions

1. What should be returned if the value isn’t found in the BST? Return None.

2. Are there duplicate values in the BST? No, a BST by definition does not contain duplicate values.

3. Can we assume the input tree is valid? Yes, you can assume the input is a valid BST.

4. What is the expected time complexity? Aim for O(h), where h is the height of the tree.

Strategy

1. BST Properties: For a given node, all left descendants are smaller and all right descendants are larger.
2. Traversal: We can utilize BST properties to efficiently search for the value.
   • Start at the root.
   • If the root matches val, return the root.
   • If val is less than the root’s value, search in the left subtree.
   • If val is more than the root’s value, search in the right subtree.
3. Recursion vs Iteration: Both approaches are acceptable. We’ll demonstrate the recursive approach here.

Code

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        # Base case: root is None or root's value matches val
        if root is None or root.val == val:
            return root
        
        # If val is less than root's val, search in the left subtree
        if val < root.val:
            return self.searchBST(root.left, val)
        
        # If val is greater than root's val, search in the right subtree
        return self.searchBST(root.right, val)

# Example usage:
# root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7))
# val = 2
# solution = Solution()
# result = solution.searchBST(root, val)
# Result should point to the subtree rooted at node with value 2

Time Complexity

• Time Complexity: The search operation in a BST has O(h) time complexity, where h is the height of the tree. In the worst case, this can be O(n) for a degenerate tree (similar to a linked list), but for a balanced BST, it’s O(log n).
• Space Complexity: The space complexity for the recursive approach is O(h) due to the recursion stack. For an iterative approach, the space complexity could be reduced to O(1).

In summary, the provided method has an efficient search implementation leveraging the properties of binary search trees.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?