Show problems as
Classic problem #501EasyTreeDepth-First SearchBinary Search TreeBinary Tree

Find Mode in Binary Search Tree

Real-world version: Most Common Gauge Offset
Tracked in this browser only
Read Find Mode in Binary Search Tree on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A calibration bench measures an integer offset, in tenths of a micron, for every gauge block it checks, and files each offset into an ordered tree. Repeats are kept, so the same offset can be filed many times over. The order rule is: for any filed offset, every offset in the branch to its left is less than or equal to it, and every offset in the branch to its right is greater than or equal to it.

The tree arrives as gauge, a level-order listing. Its first entry is the offset at the top of the tree. After that, the listing gives the left branch then the right branch of each offset already listed, in the order those offsets appear, writing null where a branch is empty. Slots below a null are never written down, and the trailing run of null entries is left off.

Work out how many times each distinct offset was filed. Return every offset whose count equals the highest count reached by any offset, listed in ascending order. Several offsets may be tied on the highest count, in which case all of them belong in the answer.

Examples

Example 1

Input
gauge = [4, 2, 7, 2, null, 7]
Output
[2, 7]

The tree holds the offsets 2, 2, 4, 7 and 7. Both 2 and 7 were filed twice while 4 was filed once, so the highest count is 2 and both offsets that reach it come back in ascending order.

Example 2

Input
gauge = [6, 6, 6, 6]
Output
[6]

All four filed offsets are 6, so 6 has a count of 4 and nothing else was filed at all.

Example 3

Input
gauge = [-3, -7, -3, -9, -5, -3]
Output
[-3]

The tree holds -9, -7, -5, -3, -3 and -3. The offset -3 was filed three times and every other offset once, so -3 is the only one at the highest count.

Constraints

  • The number of offsets filed in the tree is in the range [1, 10^4].
  • 1 <= gauge.length <= 2 * 10^4
  • -10^5 <= gauge[i] <= 10^5
  • An entry of gauge that is null marks an empty branch rather than an offset.
  • gauge[0] is never null.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def most_common_offsets(gauge: list[int | None]) -> list[int]:
Java
public int[] mostCommonOffsets(Integer[] gauge)

More on the same topics