C++ O(n) time and O(1) space by inorder traversal

  • 1

    The basic idea is that the inorder traversal of the BST is in ascending order. For example, the inorder traversal of the BST [2, 1, 3] is [1, 2, 3]. Then we can easily find the most frequently occurred elements by comparing the successive elements.

    class Solution {
        int maxFreq = 0, currFreq = 0, precursor = INT_MIN;
        vector<int> res;
        vector<int> findMode(TreeNode *root)
            return res;
        void inorderTraversal(TreeNode *root)
            if (root == NULL) return; // Stop condition
            inorderTraversal(root->left); // Traverse left subtree
            if (precursor == root->val) currFreq++;
            else currFreq = 1;
            if (currFreq > maxFreq)
            {// Current node value has higher frequency than any previous visited
                maxFreq = currFreq;
            else if (currFreq == maxFreq)
            {// Current node value has a frequency equal to the highest of previous visited
            precursor = root->val; // Update the precursor
            inorderTraversal(root->right); // Traverse right subtree

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.