A warehouse stores part numbers in a binary search tree with distinct values (every value in a left subtree is smaller than the node, every value in a right subtree is larger). Given the root and a part number val, return the node that holds val, which also represents the whole subtree below it. Return None if the part is not stored.
Examples
20
/ \
10 30
/ \ / \
5 15 25 40
Input: root = build_tree([20, 10, 30, 5, 15, 25, 40]), val = 30
Output: tree_to_list(...) == [30, 25, 40]
Input: root = build_tree([20, 10, 30, 5, 15, 25, 40]), val = 17
Output: [] (None, which tree_to_list shows as [])
Constraints
0 <= number of nodes <= 2000- All values are distinct integers
- Aim for O(h) time, where
his the height of the tree
Goals
- Use the ordering rule to discard half of the tree at every step
- Return a node (and so its whole subtree) rather than a copy