How to Find the Mode in a Binary Search Tree?


bst How to Find the Mode in a Binary Search Tree? algorithms BFS c / c++ code coding exercise data structure DFS programming languages

Binary Search Tree

Given a BST (Binary Search Tree) with duplicates, find its mode(s) – the most frequently occurred element. A BST has the following characteristics:

  • 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 left or right subtrees are also BSTs.

For example, Given BST [1, null, 2, 2] that represents the following BST:

   1
    \
     2
    /
   2

The mode is [2].

Breadth First Search

The BFS (Breadth First Search) travels the BST tree level by level. It employs a queue and at each iteration, expanding the child nodes of the current node at the head of the queue and insert them into queue.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> findMode(TreeNode* root) {        
        if (root == NULL) return {};
        unordered_map<int, int> count;
        queue<TreeNode*> Q;
        Q.push(root);
        int maxfreq = 0;
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();
            if (count.find(p->val) == count.end()) {
                count[p->val] = 1;
            } else {
                count[p->val]++; // update frequency
            }
            maxfreq = max(maxfreq, count[p->val]);
            // expand the child nodes
            if (p->left) Q.push(p->left);
            if (p->right) Q.push(p->right);            
        }
        vector<int> r;
        for (auto it = count.begin(); it != count.end(); ++ it) {
            if (it->second == maxfreq) {
                // find the mode                        
                r.push_back(it->first);
            }
        }
        return r;
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> findMode(TreeNode* root) {        
        if (root == NULL) return {};
        unordered_map<int, int> count;
        queue<TreeNode*> Q;
        Q.push(root);
        int maxfreq = 0;
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();
            if (count.find(p->val) == count.end()) {
                count[p->val] = 1;
            } else {
                count[p->val]++; // update frequency
            }
            maxfreq = max(maxfreq, count[p->val]);
            // expand the child nodes
            if (p->left) Q.push(p->left);
            if (p->right) Q.push(p->right);            
        }
        vector<int> r;
        for (auto it = count.begin(); it != count.end(); ++ it) {
            if (it->second == maxfreq) {
                // find the mode                        
                r.push_back(it->first);
            }
        }
        return r;
    }
};

Meantime, we have a hash table to count the number of occurrences for each node, and iterate the hash table to find out the modes.

Depth First Search

DFS (Depth First Search) is usually implemented via recursion, although it can be in BFS as well – where you need to push the right node first and then left node, as the stack is First In Last Out.

The DFS travels the tree in-order sequence – root, left and right. We can have a reference vector to store the nodes when they are visited.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:    
    void dfs(TreeNode* root, vector<int> &r) {
        if (root == NULL) {
            return ;
        }
        r.push_back(root->val);
        if (root->left) {
            dfs(root->left, r);            
        }
        if (root->right) {            
            dfs(root->right, r);
        }        
    }
    
    vector<int> findMode(TreeNode* root) {
        vector<int> rr;
        dfs(root, rr);
        int cnt = 0;
        unordered_map<int, int> data;        
        for (const auto &n: rr) {
            if (data.find(n) == data.end()) {
                data[n] = 1;
            } else {
                data[n] += 1; // update the frequency
            }
            cnt = max(cnt, data[n]);
        }        
        vector<int> result;
        for (auto iter = data.begin(); iter != data.end(); ++ iter) {
            if (iter->second == cnt) {
                result.push_back(iter->first);
            }
        }
        return result;
    }
};
class Solution {
public:    
    void dfs(TreeNode* root, vector<int> &r) {
        if (root == NULL) {
            return ;
        }
        r.push_back(root->val);
        if (root->left) {
            dfs(root->left, r);            
        }
        if (root->right) {            
            dfs(root->right, r);
        }        
    }
    
    vector<int> findMode(TreeNode* root) {
        vector<int> rr;
        dfs(root, rr);
        int cnt = 0;
        unordered_map<int, int> data;        
        for (const auto &n: rr) {
            if (data.find(n) == data.end()) {
                data[n] = 1;
            } else {
                data[n] += 1; // update the frequency
            }
            cnt = max(cnt, data[n]);
        }        
        vector<int> result;
        for (auto iter = data.begin(); iter != data.end(); ++ iter) {
            if (iter->second == cnt) {
                result.push_back(iter->first);
            }
        }
        return result;
    }
};

Alternatively, the recursion function can return the nodes as they are visited.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:    
    vector<int> dfs(TreeNode* root) {
        if (root == NULL) {
            return {};
        }
        vector<int> r = { root->val };
        if (root->left) {
            // DFS of left tree
            auto a = dfs(root->left);
            // add it to the current result set
            r.insert(r.end(), a.begin(), a.end());
        }
        if (root->right) {            
            // DFS of the right tree
            auto b = dfs(root->right);
            // add it to the current result set
            r.insert(r.end(), b.begin(), b.end());
        }
        return r;
    }
    
    vector<int> findMode(TreeNode* root) {
        auto rr = dfs(root);
        int cnt = 0;
        unordered_map<int, int> data;        
        for (const auto &n: rr) {
            if (data.find(n) == data.end()) {
                data[n] = 1;
            } else {
                data[n] += 1;
            }
            cnt = max(cnt, data[n]);
        }        
        vector<int> result;
        for (auto iter = data.begin(); iter != data.end(); ++ iter) {
            if (iter->second == cnt) {
                result.push_back(iter->first);
            }
        }
        return result;
    }
};
class Solution {
public:    
    vector<int> dfs(TreeNode* root) {
        if (root == NULL) {
            return {};
        }
        vector<int> r = { root->val };
        if (root->left) {
            // DFS of left tree
            auto a = dfs(root->left);
            // add it to the current result set
            r.insert(r.end(), a.begin(), a.end());
        }
        if (root->right) {            
            // DFS of the right tree
            auto b = dfs(root->right);
            // add it to the current result set
            r.insert(r.end(), b.begin(), b.end());
        }
        return r;
    }
    
    vector<int> findMode(TreeNode* root) {
        auto rr = dfs(root);
        int cnt = 0;
        unordered_map<int, int> data;        
        for (const auto &n: rr) {
            if (data.find(n) == data.end()) {
                data[n] = 1;
            } else {
                data[n] += 1;
            }
            cnt = max(cnt, data[n]);
        }        
        vector<int> result;
        for (auto iter = data.begin(); iter != data.end(); ++ iter) {
            if (iter->second == cnt) {
                result.push_back(iter->first);
            }
        }
        return result;
    }
};

Both C++ methods are O(N) complexity as they all need to travel all the nodes in the BST Tree. The DFS has average O(N logN + N) space complexity i.e as the tree ‘s depth is O(N LogN) and the hash table to count the frequency is O(N). The BFS approach requires the use of a queue while the DFS recursion allocates the stacks.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
846 words
Last Post: A Simple PHP Command Line Tool to Convert MySQL Tables from MyISAM to InnoDB in Specified Database
Next Post: How to restore SQL database backup by using SQL Server Management Studio?

The Permanent URL is: How to Find the Mode in a Binary Search Tree?

Leave a Reply