428 binary tree (501. mode in binary search tree, 701. insert operation in binary search tree, 450. delete node in binary search tree, 669. prune binary search tree)

501. The mode in the binary search tree

class Solution {
    
public:
    void search_bst(TreeNode* cur, unordered_map<int, int>& mp)
    {
    
        if (cur == nullptr)  return;
        mp[cur->val]++;
        search_bst(cur->left, mp);
        search_bst(cur->right, mp);
    }
public:
    vector<int> findMode(TreeNode* root) {
    
        unordered_map<int, int> mp;
        vector<int> res;
        if (root == nullptr) return res;
        search_bst(root, mp);

        vector<pair<int, int>> vec(mp.begin(), mp.end());
        sort(vec.begin(), vec.end(),
            [](const pair<int, int>& x, const pair<int, int>& y) -> bool
            {
    
                return x.second > y.second;
            });

        res.push_back(vec[0].first);
        for (int i = 1; i < vec.size(); i++)
        {
    
            if (vec[i].second == vec[0].second)  res.push_back(vec[i].first);
            else break;
        }
        return res;
    }
};

701. Insert operation in binary search tree

class Solution {
    
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
    
        if (root == nullptr)
        {
    
            TreeNode* node = new TreeNode(val);
            return node;
        }

        if (root->val > val) root->left = insertIntoBST(root->left, val);
        if (root->val < val) root->right = insertIntoBST(root->right, val);

        return root;
    }
};

450. Delete nodes in binary search tree

class Solution {
    
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
    
        if (root == nullptr) return root;
        if (root->val == key)
        {
    
            if (root->left == nullptr && root->right == nullptr)
            {
    
                delete root;
                return nullptr;
            }
            else if (root->left == nullptr)
            {
    
                TreeNode* retNode = root->right;
                delete root;
                return retNode;
            }
            else if (root->right == nullptr)
            {
    
                TreeNode* retNode = root->left;
                delete root;
                return retNode;
            }
            else
            {
    
                TreeNode* cur = root->right;
                while (cur->left != nullptr)
                {
    
                    cur = cur->left;
                }
                cur->left = root->left;
                TreeNode* tmp = root;
                root = root->right;
                delete tmp;
                return root;
            }
        }
        if (root->val > key) root->left = deleteNode(root->left, key);
        if (root->val < key)  root->right = deleteNode(root->right, key);

        return root;
    }
};

669. Prune the binary search tree

class Solution {
    
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
    
        if (root == nullptr) return nullptr;
        if (root->val < low)
        {
    
            TreeNode* right = trimBST(root->right, low, high);
            return right;
        }
        if (root->val > high)
        {
    
            TreeNode* left = trimBST(root->left, low, high);
            return left;
        }
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);

        return root;
    }
};