Problem
Given the root of a Binary Search Tree and an integer val, find the node in the tree whose value is equal toval.
If the node exists, return the subtree rooted at that node. If the value does not exist in the tree, return
null.
In a BST, values smaller than the current node are located in the left subtree, while values greater than the current node are located in the right subtree.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
root:
4
/ \
2 7
/ \
1 3
val = 2Output
2
/ \
1 3Example 2
Input
root:
4
/ \
2 7
/ \
1 3
val = 5Output
nullSolution
This solution uses the Binary Search Tree property to search for the target value. If the current node isnull, the value does not exist in the tree. If the current node's value matches the target, we return the current node.
If the target value is greater than the current node's value, we recursively search the right subtree. Otherwise, we search the left subtree. This avoids traversing branches that cannot contain the target value.
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if (root == null) {
return null;
}
if (root.val == val) {
return root;
}
if (root.val < val) {
return searchBST(root.right, val);
} else {
return searchBST(root.left, val);
}
}
}Complexity
At each step, we move to only one subtree, so the time complexity isO(h), where h is the height of the tree. For a balanced BST, this is O(log n)O(n).
The recursive calls use space proportional to the height of the tree, so the extra space complexity is
O(h).