Mode in Binary Search Tree#

Given a binary search tree (BST) with the same values, find all modes in the BST (the elements with the highest frequency).

Assume that the BST is defined as follows:

• The values in the nodes of the left subtree are less than or equal to the value of the current node.
• The values in the nodes of the right subtree are greater than or equal to the value of the current node.
• Both the left subtree and the right subtree are binary search trees.

Example#

Given the BST [1,null,2,2], return [2].

Note#

Note: If there are more than 1 mode, the output order is not considered. Advanced: Can you solve it without using extra space? (Assume that the overhead of the implicitly called stack produced by recursion is not counted).

Solution#

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var findMode = function(root) {
    if(!root) return [];
    var cur = Infinity;
    var curCounter = 0;
    var maxValues = [];
    var maxValuesCounter = -Infinity;
    var dfs = (root) => {
        if(!root) return void 0;
        if(root.left) dfs(root.left);
        if(cur === root.val){
            ++curCounter;
        }else{
            cur = root.val;
            curCounter = 0;
        }
        if(curCounter >= maxValuesCounter){
            if(curCounter === maxValuesCounter) maxValues.push(root.val);
            else maxValues = [root.val];
            maxValuesCounter = curCounter;
        }
        if(root.right) dfs(root.right);
    }
    dfs(root);
    return maxValues;
};

Idea#

In this problem, there is an advanced condition: Can you solve it without using extra space? (Assume that the overhead of the implicitly called stack produced by recursion is not counted). If not considering this advanced condition, we can simply traverse the binary tree once and use a hash map to record the visited values and their frequencies. Then, we can iterate over the hash map to get the modes. Considering this advanced condition, we need to define some variables to store the current state, determine which conditions meet the requirements, and output the return values. By traversing the binary search tree in an in-order manner, we can obtain an ordered sequence. By using variables to store the current state, we can achieve the goal. Additionally, it is important to note that the problem requires returning an array, which means there may be multiple modes. First, we check if it is an empty tree and return an empty array. We define the current value as Infinity, the current value counter as 0, the array for the maximum values as an empty array, and the counter for the maximum values as -Infinity. Then, we define a depth-first search (DFS) to traverse. First, we check if the node does not exist, and if so, return. If the left node exists, we recursively traverse to the left. The processing at this position is an in-order traversal. If the current node value is the same as the stored value, we increment the counter; otherwise, we set the current value to the value of the node and reset the counter to 0. If the current counter is greater than or equal to the maximum value counter, we enter the condition. If these two values are equal, the value is added to the array of maximum values; otherwise, the array of maximum values is replaced with an array containing only this value. Then, we set the maximum value counter to the current value counter. Finally, if the right node exists, we recursively traverse to the right, and return the array of maximum values in the end.

Daily Question#

Reference#