Problem

Given a Binary Search Tree (BST), find the mode (most frequently occurring value). Requirement: Apart from the recursion stack space, the space complexity should be O(1).

Analysis

Clearly, an in-order traversal of a binary search tree produces a sorted array. Finding the mode in a sorted array means looking for the longest sequence of consecutive repeated numbers. Note that the problem requires returning all modes if there are multiple values with the same highest frequency. Additionally, the space complexity must be O(1). Writing code that meets these requirements is not difficult.

Runtime: 16ms, beats 62% of submissions

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */


class Solution {
private:
    vector<int> mode;
    int last;
    int lastCount;
    int modeCount;
public:
    vector<int> findMode(TreeNode* root) {
        last = 0;
        lastCount = 0;
        modeCount = 0;
        mode.clear();
        runMode(root);
        return mode;
    }

    void runMode(TreeNode* root){
        if(root != NULL){
            runMode(root -> left);
            int nowValue = root->val;
            int nowCount = nowValue != last? 1 : lastCount + 1;
            if(modeCount == nowCount){
                mode.push_back(nowValue);
            }
            if(modeCount < nowCount){
                modeCount = nowCount;
                mode.clear();
                mode.push_back(nowValue);
            }
            last = nowValue;
            lastCount = nowCount;
            runMode(root -> right);
        }
    }
    
};