Find Mode in Binary Search Tree

                                            
var findMode = function(root) {
  const memo = {}

  const dfs = (n) =>{
    if(!n) return;
      
    dfs(n.left);
    dfs(n.right);
    if(n.val in memo){
      memo[n.val]++;
    }else{
      memo[n.val] = 1;
    }
    
  }
    dfs(root)
  const arr = Object.entries(memo).sort((a,b)=> b[1] - a[1]);
  let ans = [];
  
  for(let i=0; i<arr.length; i++){
    if(arr[i][1] === arr[0][1]){
      ans.push(arr[i][0])
    }else{
      break; 
    }
  }
  return ans;
};

The provided solution finds the mode(s) in a Binary Search Tree (BST) using a depth-first search (DFS) traversal and a hashmap (or object in JavaScript) to keep track of the frequency of each value encountered in the tree. Here's a step-by-step explanation followed by pseudo code:

Explanation:

1. Define a hashmap (memo):

This hashmap is used to store the frequency of each value encountered in the tree. The keys are the node values, and the values are their respective counts.

2. Depth-First Search (DFS) function:

The dfs function is defined to traverse the tree. It's a recursive function that visits every node in the tree, starting from the root.

3. Recursive DFS traversal:

For each node visited, the function recursively calls itself on the left and right children of the node (if they exist), ensuring that all nodes in the tree are visited.

4. Update hashmap:

After visiting a node's children, the function updates the hashmap with the current node's value. If the value is already in the hashmap, its count is incremented. Otherwise, it's added to the hashmap with a count of 1.

5. Sorting and finding modes:

After the DFS traversal is complete, the entries in the hashmap are sorted in descending order by their frequency. The highest frequency (or frequencies, in case of a tie) determines the mode(s) of the tree.

6. Constructing the result:

The function then iterates through the sorted array of frequencies. It adds the values with the highest frequency to the result array. The iteration stops as soon as a value with a lower frequency is encountered, as the array is sorted.

7. Return result:

Finally, the function returns the result array, which contains the mode(s) of the BST.

Pseudo Code:

                                        
function findMode(root):
    Initialize a hashmap (memo) to store value frequencies
    Define a DFS function (dfs) that takes a node (n) as its argument

    DFS function (n):
        if n is null, return
        Call DFS on n.left (left child)
        Call DFS on n.right (right child)
        Update memo with n.val (increment if exists, set to 1 if not)

    Call DFS with root node
    Convert memo to an array of [value, frequency] pairs and sort it in descending order by frequency
    Initialize an empty array (ans) for storing modes
    Iterate through the sorted array:
        if current frequency equals the highest frequency, add the value to ans
        else, break the loop
    Return ans

Note on Space Complexity:

The follow-up question asks if it's possible to solve this without using any extra space. The provided solution does use extra space for the hashmap and the sorted array. An in-order traversal could be used to leverage the properties of the BST to find modes without extra space, but this would require a more complex approach to keep track of the current count, maximum count, and modes as you traverse.