Problem Description

Given the root of a binary search tree (BST) and an integer target, split the BST into two subtrees:

• One subtree contains all nodes with values less than or equal to target.
• The other subtree contains all nodes with values greater than target.

Both resulting subtrees should maintain the properties of a BST. The function should return the roots of these two subtrees as a list or array of two elements. You must not reuse or duplicate any nodes — each node from the original tree should appear in exactly one of the resulting subtrees.

There is exactly one valid way to split the BST for a given target, and you do not need to balance the trees after splitting.

Thought Process

To solve this problem, let's first consider the unique properties of a BST:

• For any node, all nodes in the left subtree have values less than the node's value.
• All nodes in the right subtree have values greater than the node's value.

• If the node's value is less than or equal to target, it belongs in the "small" tree, and we may need to split its right subtree.
• If the node's value is greater than target, it belongs in the "large" tree, and we may need to split its left subtree.

Solution Approach

We'll use a recursive function that, given a node and the target, returns two roots: the root of the "small" BST (all values ≤ target) and the root of the "large" BST (all values > target).

1. Base Case: If the current node is null, return [null, null] — both subtrees are empty.
2. Recursive Case:
   • If node.val ≤ target:
     • The current node and its left subtree belong to the "small" tree.
     • Recursively split the right subtree with the same target.
     • Attach the "small" part of the right subtree as the right child of the current node.
     • Return [current node, large subtree from right].
   • If node.val > target:
     • The current node and its right subtree belong to the "large" tree.
     • Recursively split the left subtree with the same target.
     • Attach the "large" part of the left subtree as the left child of the current node.
     • Return [small subtree from left, current node].
3. Return: The two roots representing the two BSTs.

This approach is efficient because each node is visited only once, and we only modify pointers.

Example Walkthrough

Suppose the BST is:

        4
       / \
      2   6
     / \ / \
    1  3 5  7
  

Let target = 2. We want to split the tree into:

• All nodes ≤ 2: should include 1 and 2.
• All nodes > 2: should include 3, 4, 5, 6, 7.

1. Start at root (4): 4 > 2, so split left subtree (2) with target 2.
2. At node 2: 2 ≤ 2, so split right subtree (3). 3 > 2, so its left is null, its right is null. Return [null, 3]. Attach null to 2's right.
3. Return [2, 3] for node 2.
4. Back at 4: Attach 3 (from right of 2) as left child of 4. Return [2, 4].

• First tree (≤ 2): 2 with left child 1.
• Second tree (> 2): 4 with left child 3, right subtree unchanged.

Time and Space Complexity

Brute-force approach: If we were to traverse the tree and insert each node into a new BST, the time complexity would be O(N log N) (for N insertions), and space complexity would be O(N) due to new nodes.

Optimized recursive approach: Each node is visited exactly once, so time complexity is O(N), where N is the number of nodes. Space complexity is O(H), where H is the height of the tree, due to the recursion stack.

Summary

The key insight for splitting a BST is to use its structure and recursion: at each node, decide which subtree it belongs to based on the target, and recursively split only the necessary subtrees. This ensures both efficiency and correctness, with no need to create new nodes or extra data structures. The elegance of this solution lies in its simplicity and the direct use of BST properties.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def splitBST(self, root, target):
        if not root:
            return [None, None]
        if root.val <= target:
            small, large = self.splitBST(root.right, target)
            root.right = small
            return [root, large]
        else:
            small, large = self.splitBST(root.left, target)
            root.left = large
            return [small, root]
      

/**
 * 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<TreeNode*> splitBST(TreeNode* root, int target) {
        if (!root) return {nullptr, nullptr};
        if (root->val <= target) {
            auto splitted = splitBST(root->right, target);
            root->right = splitted[0];
            return {root, splitted[1]};
        } else {
            auto splitted = splitBST(root->left, target);
            root->left = splitted[1];
            return {splitted[0], root};
        }
    }
};
      

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode[] splitBST(TreeNode root, int target) {
        if (root == null) return new TreeNode[]{null, null};
        if (root.val <= target) {
            TreeNode[] splitted = splitBST(root.right, target);
            root.right = splitted[0];
            return new TreeNode[]{root, splitted[1]};
        } else {
            TreeNode[] splitted = splitBST(root.left, target);
            root.left = splitted[1];
            return new TreeNode[]{splitted[0], root};
        }
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} target
 * @return {[TreeNode, TreeNode]}
 */
var splitBST = function(root, target) {
    if (!root) return [null, null];
    if (root.val <= target) {
        let [small, large] = splitBST(root.right, target);
        root.right = small;
        return [root, large];
    } else {
        let [small, large] = splitBST(root.left, target);
        root.left = large;
        return [small, root];
    }
};