700. Search in a Binary Search Tree
Model: qwen2.5-coder:14b
Topics: Tree
FAANG asked: 1
Acceptance rate: 73.4%
Problem Breakdown
The problem requires finding a node in a binary search tree (BST) where the node’s value matches a given integer val. If such a node exists, we return the subtree rooted at that node. If no such node exists, we return null.
Inputs:
root: The root node of the BST.val: An integer value to search for in the BST.
Outputs:
- The subtree rooted at the node with value
val, ornullif no such node exists.
Implicit Constraints/Edge Cases:
- The tree can be empty, though the problem guarantees at least one node.
- The values are unique within the BST.
Intuition
A brute-force approach would involve traversing the entire tree to find the node with value val. This would have a time complexity of O(n), where n is the number of nodes in the tree. However, since it’s a binary search tree, we can leverage its properties to improve efficiency.
The key insight is that for any given node in a BST:
- If the target value
valis less than the current node’s value, then the target must be in the left subtree. - If the target value
valis greater than the current node’s value, then the target must be in the right subtree.
This allows us to perform a binary search-like traversal, reducing the time complexity to O(h), where h is the height of the tree. In the worst case (a skewed tree), this could still be O(n), but for a balanced BST, it would be O(log n).
Approach
We will use an iterative approach with a stack to traverse the BST. The steps are as follows:
- Initialize a stack and push the root node onto it.
- While the stack is not empty:
- Pop a node from the stack.
- If the node’s value matches
val, return the node (which represents the subtree). - If
valis less than the node’s value, push the left child onto the stack if it exists. - If
valis greater than the node’s value, push the right child onto the stack if it exists.
- If we exit the loop without finding the node, return
null.
Complexity Analysis
- Time Complexity: O(h), where h is the height of the tree. In the worst case (a skewed tree), this could be O(n). For a balanced BST, it would be O(log n).
- Space Complexity: O(h) due to the stack used for traversal. In the worst case, this could be O(n).
Solution
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def searchBST(root: TreeNode, val: int) -> TreeNode:
stack = [root]
while stack:
node = stack.pop()
if node.val == val:
return node
if node.val > val and node.left:
stack.append(node.left)
if node.val < val and node.right:
stack.append(node.right)
return None
Edge Cases Handled
- Empty Tree: The function will return
nullimmediately since the root isNone. - Node Not Found: If no node with value
valexists in the tree, the function will traverse the entire tree and finally returnnull.