Advanced binary tree problems

Most binary tree problems can be solved recursively. In this article, I’d like to list some binary tree problems which may need some extra efforts to figure everything out.

776. Split BST

Solve it recursively

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> splitBST(TreeNode* root, int V) {
        vector<TreeNode*> ret;
        if (!root) return {nullptr, nullptr};
        if (root->val == V) {
            auto right = root->right;
            root->right = nullptr;
            ret.push_back(root);
            ret.push_back(right);
            return ret;
        }
        else {
            if (root->val > V) {
                auto left = splitBST(root->left, V);
                root->left = left[1];
                ret.push_back(left[0]);
                ret.push_back(root);
                return ret;
            }
            else {
                auto right = splitBST(root->right, V);
                root->right = right[0];
                ret.push_back(root);
                ret.push_back(right[1]);
                return ret;
            }
        }
    }
};