501. Find in the Search Tree
A seed vault keeps its crates in a binary search tree ordered by crate number. For every node, all keys in its left subtree are smaller than the node's key, all keys in its right subtree are larger, and no key occurs twice.
Given the tree root and an integer value, locate the node whose key equals value and return that node itself (the node together with everything below it, not just the number). If no node carries that key, or the tree is empty, return null. The tree must not be changed.
Example 1
- Input:
- root = [40,20,60,10,30,50,70], value = 50
- Output:
- 5
- Explanation:
Going right from 40 then left from 60 reaches the node with key 50, which has no children.
Example 2
- Input:
- root = [40,20,60,10,30,50,70], value = 45
- Output:
- null
- Explanation:
The search goes right at 40, left at 60, then right at 50 and falls off the tree, so the answer is null.
Constraints
0 ≤ number of nodes ≤ 104
-109 ≤ Node.val, value ≤ 109
The tree is a valid binary search tree and all keys are distinct.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(h)
- Space
- O(1)