388. Find Mode in Binary Search Tree
You are given the root of a binary search tree that allows duplicates: every value in a node's left subtree is <= the node's value, and every value in its right subtree is >= it.
Return every value that occurs more often than any other — the mode(s) of the tree. Several values can tie for the highest count; return all of them, in increasing order.
A hash map makes this easy. Can you also do it with no map at all, using only the BST ordering?
Example 1:
Input: root = [1, null, 2, 2]
Output: [2]
Explanation: The value 2 appears twice and 1 appears once, so 2 is the unique mode.
Example 2:
Input: root = [5, 3, 6, 3, 4, 6]
Output: [3, 6]
Explanation: Both 3 and 6 appear twice while 4 and 5 appear once, so the modes are [3, 6] in increasing order.
Constraints:
- 1 ≤ number of nodes ≤ 10⁴
- -10⁵ ≤ Node.val ≤ 10⁵
- Duplicates respect the BST rule: left subtree values ≤ node value ≤ right subtree values.
Hints:
Any traversal plus a value → count hash map solves this in one pass. Take the maximum count, then collect every value that reaches it.
An inorder traversal of a BST visits values in sorted order, so equal values arrive back to back. Track the previous value and the length of the current run — a run as long as the best so far is a mode. No map needed.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [1, null, 2, 2]
Expected output: [2]