---
tags: leetcode
---

# [776. Split BST](https://leetcode.com/problems/split-bst/)
---
# My Solution
## The Key Idea for Solving This Coding Question
## C++ Code

/**
 * 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 target) {
        if (root == nullptr) {
            return {nullptr, nullptr};
        }

        if (root->val <= target) {
            // Because root->val is less than or equal to target, 
            // we need to split the right subtree. Therefore, go 
            // to the right subtree.
            vector<TreeNode *> bstPair = splitBST(root->right, target);

            // Because the right subtree (root->right) has been splited,
            // we need to find the new root of the right subtree.
            // Both bstPair[0] and bstPair[1] have greater node values 
            // than root->val, so we can pick either bstPair[0] or 
            // bstPair[1] to the new root of the right subtree. 
            // However, bstPait[1] has greater node values than target.
            // Therefore, we choose bstPair[0] to be the new root of 
            // the right subtree.
            root->right = bstPair[0];
            bstPair[0] = root;
            return bstPair;
        }
        // target < root->val is true.

        // Because root->val is greater than target, we need to 
        // split the left subtree. Therefore, go to the left subtree.
        vector<TreeNode *> bstPair2 = splitBST(root->left, target);
        
        root->left = bstPair2[1];
        bstPair2[1] = root;
        return bstPair2;
    }
};

## Time Complexity
$O(H)$
$H$ is the height of the BST.
## Space Complexity
$O(H)$
$H$ is the height of the BST.
# Miscellane
<!--
# Test Cases

[4,2,6,1,3,5,7]
2

[1]
1

[4,2,6,1,3,5,7]
100

[4,2,6,1,3,5,7]
0

-->