LeetCode: 501. Find Mode in Binary Search Tree

The Problem

Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.

If the tree has more than one mode, return them in any order.

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than or equal to the node's key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
• Both the left and right subtrees must also be binary search trees.

Example:

Input:  [1,null,2,2]
Output: [2]

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

vector<int> findMode(TreeNode* root) {
    vector<int> modes;
    int maxValue = 0, currCount = 0;
    int prevVal = INT_MIN;

    transverse( modes,root, maxValue, currCount, prevVal );

    return modes;
}

void transverse(
    vector<int> &modes, TreeNode *root,
    int &maxValue, int &currCount, int &prevVal
){

    if( root == nullptr ) return;

    TreeNode *left = root->left;
    transverse( modes, root->left, maxValue, currCount, prevVal );

    if ( root->val == prevVal ) ++currCount;
    else currCount = 1;

    if( currCount == maxValue ) { 
    	modes.emplace_back(root->val);
    } else if( currCount > maxValue ) {
        modes.clear();
        modes.emplace_back(root->val);
        maxValue = currCount;
    }

    prevVal = root->val;

    TreeNode *right = root->right;
    transverse(modes, right, maxValue, currCount, prevVal);
}

This function performs an in-order traversal of the binary tree and calculates the mode(s). Here's how it works:

• if( root == nullptr ) return;: If the current node is null (empty), the function stops and returns.
• transverse(modes, root->left, maxValue, currCount, prevVal);: Recursively traverse the left subtree.
• if ( root->val == prevVal ) ++currCount;: If the current node's value is the same as the previous value encountered, increment the current count. This helps to keep track of consecutive occurrences of the same value.
• else currCount = 1;: If the current value is different from the previous value, reset the current count to 1.
• if( currCount == maxValue ): If the current count matches the maximum frequency encountered so far, add the current value to the modes vector.
• else if( currCount > maxValue ): If the current count surpasses the maximum frequency encountered, clear the modes vector and update it with the current value. Also, update maxValue with the new maximum frequency.
• prevVal = root->val;: Update prevVal with the current value for the next iteration.
• transverse(modes, right, maxValue, currCount, prevVal);: Recursively traverse the right subtree.

Overall, this code counts the frequency of each value during the traversal and identifies the mode(s) of the binary tree by maintaining counts and comparing them to find the maximum frequency.