algoadvance

Leetcode 501. Find Mode in Binary Search Tree

Problem Statement

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

Clarifying Questions

  1. Input Validation: Can the tree have negative values or zeroes?
    • Yes, the tree can contain any integer values.
  2. Output Format: If multiple modes exist, how should they be returned?
    • Return the modes as a vector of integers.
  3. Constraints:
    • The number of nodes in the tree is in the range [1, 10^4].
    • -10^5 <= Node.val <= 10^5.

Strategy

  1. In-Order Traversal: Utilize the properties of BST where an in-order traversal yields sorted values.
  2. Count Frequencies: During the traversal, keep a count of each node value.
  3. Determine Modes: Keep track of the maximum frequency and gather values having this frequency.

Approach

  1. Perform an in-order traversal to access the elements in a sorted manner.
  2. Use a hash map (unordered_map<int, int>) to count occurrences of each value.
  3. Find the maximum frequency from the hash map.
  4. Collect all keys from the hash map that match this maximum frequency.

Code

#include <unordered_map>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        if (!root) return {};
        
        unordered_map<int, int> countMap;
        inorderTraversal(root, countMap);
        
        int maxCount = 0;
        for (const auto& pair : countMap) {
            if (pair.second > maxCount) {
                maxCount = pair.second;
            }
        }
        
        vector<int> modes;
        for (const auto& pair : countMap) {
            if (pair.second == maxCount) {
                modes.push_back(pair.first);
            }
        }
        
        return modes;
    }
    
private:
    void inorderTraversal(TreeNode* node, unordered_map<int, int>& countMap) {
        if (!node) return;
        
        inorderTraversal(node->left, countMap);
        countMap[node->val]++;
        inorderTraversal(node->right, countMap);
    }
};

Time Complexity

Overall Time Complexity: O(n)

Space Complexity

Overall Space Complexity: O(n) in the worst case due to the hashmap storing counts of all nodes.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI