Most Frequent Search Keys
EasyTrees
Problem
A survey stores answers in a binary search tree that allows duplicates: every value in a node's left subtree is ≤ the node and every value in its right subtree is ≥ the node.
Return all values that occur the most times. The order of the output does not matter.
Example 1
- Input:
- root = [1, null, 2, 2]
- Output:
- [2]
2 appears twice, 1 once.
Example 2
- Input:
- root = [5, 3, 7, 3, 5, 6, 7]
- Output:
- [3, 5, 7]
3, 5 and 7 each appear twice; 6 once.
Example 3
- Input:
- root = [0]
- Output:
- [0]
Constraints
- 1 ≤ number of nodes ≤ 10^4
- -10^5 ≤ node.val ≤ 10^5
Hint
Show the first hint
Where are equal values located relative to each other in in-order traversal?
Walkthrough
How to approach it
01Clarify before coding
- Is the duplicate rule ≤ on the left and ≥ on the right? Yes, so in-order is non-decreasing.
- Can several values tie? Yes, return them all in any order.
- Can I use a hash map? Yes, but the in-order run approach needs no map.
02Brute force
Traverse the tree, count values in a hash map, then pick the keys with the maximum count.
Cost: O(n) time but O(n) extra space for the map; it ignores the ordering.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.