Search for a command to run...
What it teaches: Following one path down the tree using the ordering.
Practise it on judges as “Search in a Binary Search Tree”.
Return the subtree rooted at the node whose value equals val, or null if there is no such node.
Example 1
Input: root = [4, 2, 7, 1, 3], val = 2 Output: [2, 1, 3]
Example 2
Input: root = [4, 2, 7, 1, 3], val = 5 Output: []
Constraints
Pattern clues in the wording
These clues point to BST Ordering: Use left < node < right to skip half the tree, and in-order traversal to visit values in sorted order.
Stuck? Take one hint at a time
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
return null;
}
}Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.
Test cases
| # | Input | Expected |
|---|---|---|
| 1 | root = [4,2,7,1,3] val = 2 | [2,1,3] |
| 2 | root = [4,2,7,1,3] val = 5 | [] |
+ 1 hidden test the code runner will check
From slow to fast
While the node isn't null and isn't the value, move left if val is smaller, else right.
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
TreeNode cur = root;
while (cur != null && cur.val != val) cur = val < cur.val ? cur.left : cur.right;
return cur;
}
}Verdict: No recursion needed.
Before you submit
Test these inputs
Mistakes people make
Interview
How do you find the closest value to a target?