Return Every Most-Frequent Value in a Binary Search Tree

# Return Every Most-Frequent Value in a Binary Search Tree Given the root of a binary search tree that may contain duplicates, return all values that occur as often as the most frequent value. Return each such value once, in any order. The tree obeys these rules at every node: all keys in its left subtree are less than or equal to its key, all keys in its right subtree are greater than or equal to its key, and both subtrees are binary search trees. Duplicate keys may therefore occur on either side. ### Interface `class Solution { public: vector<int> findMode(TreeNode* root); };` The provided `TreeNode` has `int val` and child pointers `TreeNode* left` and `TreeNode* right`. ### Example 1 ```text Input: root = [2,1,3,1,null,3] Output: [1,3] ``` The notation is level order with `null` for a missing child: root 2 has left child 1 and right child 3; the left child has its own left child 1, and the right child has its own left child 3. Values 1 and 3 each occur twice, while 2 occurs once. `[3,1]` is also valid. ### Example 2 ```text Input: root = [5,5,5] Output: [5] ``` The root and both children have value 5, so 5 is the only mode. Equal keys in both subtrees are allowed. ### Constraints - The tree contains between 1 and 10000 nodes. - `-100000 <= Node.val <= 100000`. - The tree satisfies the duplicate-permitting BST rules stated above. ### Follow-up Can you solve this without extra space, excluding the returned values? For this follow-up, the implicit recursion stack is not counted as extra space. ### What a Strong Answer Covers - Every value tied for the highest frequency, returned once, with any output order allowed. - Duplicates in either subtree, a single node and highly skewed trees. - A correctness argument and an honest accounting of traversal and output storage. ```hint Value order How do equal values appear when a duplicate-permitting BST is read in sorted order? ```