Home | Projects | Notes > Coding Interview Questions > LC - E - 501. Find Mode in Binary Search Tree

LC - E - 501. Find Mode in Binary Search Tree

Solutions in C++

Solution 1

Complexity Analysis:

• T = O(n log n)

  • inorder(root) - O(n log n), where 'n' = number of nodes

    • Visits every node exactly once.

    • For each node, it does a map[val]++ → this is a logarithmic operation due to std::map.

  • for (auto &elem : m) to find max frequency - O(n)

    • There are at most 'n' unique values.

  • for (auto &elem : m) to collect modes - O(n)

    • There are at most 'n' unique values.

• S = O(n)

  • Map - O(n)

  • Output vector - O(n)

  • Call stack - Recursive in-order traversal

    • For a balanced tree: O(log n), for skewed tree: O(n)

Solution:

62
1
/**
2
 * Definition for a binary tree node.
3
 * struct TreeNode {
4
 *     int val;
5
 *     TreeNode *left;
6
 *     TreeNode *right;
7
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10
 * };
11
 */
12
class Solution {
13
public:
14
    vector<int> findMode(TreeNode* root) {
15
        vector<int> v;
16

17
        if (root == nullptr)
18
        {
19
            v.push_back(0);
20
            return v;
21
        }
22

23
        // populate the map
24
        inorder(root);
25

26
        // find the maximum occurrence
27
        int max = 0;
28
        for (auto &elem : m)
29
        {
30
            if (elem.second > max)
31
                max = elem.second;
32
        }
33

34
        // populate the vector with the key(s) with maximum occurrence
35
        for (auto &elem : m)
36
        {
37
            if (elem.second == max)
38
                v.push_back(elem.first);
39
        }
40

41
        return v;
42
    }
43

44
private:
45
    void inorder(TreeNode *root)
46
    {
47
        // recursively traverse the passed tree and populate the map
48

49
        // terminating condition
50
        if (root == nullptr)
51
            return;
52

53
        // recursive steps
54
        inorder(root->left);
55
        m[root->val]++;
56
        inorder(root->right);
57

58
        return;
59
    }
60

61
    std::map<int, int> m;
62
};