The Door Maze is a tree of numbered doors, and somewhere inside is the door you need. Opening every door would take ages, but the maze follows the search-tree rule: for every door, all numbers in its left subtree are smaller, and all numbers in its right subtree are bigger. No two doors share a number.
TreeNode(val, left=None, right=None) is in the starter. Keep it.
Write search_bst(root, target) -> TreeNode | None: return the node whose val is target (the door, with every door behind it), or None if no door has that number.
Then write doors_found(root, targets) -> int: a list of door numbers to check; return how many of them are in the maze. Use search_bst for each one.
# 50
# / \
# 30 70
# / \ / \
# 20 40 60 80
# / \ / \ / \ / \
# 10 25 35 42 55 65 75 90
search_bst(root, 42) # the node 42: 42 < 50 left, 42 > 30 right, 42 > 40 right, found
search_bst(root, 30) # the node 30, with 20, 40, 10, 25, 35, 42 below it
search_bst(root, 45) # None: 45 > 42, but 42 has no right child
search_bst(None, 7) # None
doors_found(root, [42, 45, 90, 1]) # 2
- Up to 70,000 doors, at most 500 levels deep. Door numbers are distinct. Door numbers and targets are integers between
-10^9and10^9. - Up to 50,000 targets in one
doors_foundcall. - Aim for O(h) per search, where
his the height of the tree. The tests count how many doors you look at.
Show hint
At each door, the target is either this door, smaller (so it can only be on the left), or bigger (only on the right). One comparison throws away a whole side.