Split BST

medium trees bst recursion

Problem

Given a BST and a value V, split it into two BSTs: one with all keys <= V and one with all keys > V, preserving the original tree structure as much as possible.

Inputroot=[4,2,6,1,3,5,7], V=2

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

Two BSTs partitioned by V=2.

input

def splitBST(root, V):
    if not root: return [None, None]
    if root.val <= V:
        left, right = splitBST(root.right, V)
        root.right = left
        return [root, right]
    else:
        left, right = splitBST(root.left, V)
        root.left = right
        return [left, root]

function splitBST(root, V) {
  if (!root) return [null, null];
  if (root.val <= V) {
    const [l, r] = splitBST(root.right, V);
    root.right = l;
    return [root, r];
  } else {
    const [l, r] = splitBST(root.left, V);
    root.left = r;
    return [l, root];
  }
}

TreeNode[] splitBST(TreeNode root, int V) {
    if (root == null) return new TreeNode[]{null, null};
    if (root.val <= V) {
        TreeNode[] p = splitBST(root.right, V);
        root.right = p[0];
        return new TreeNode[]{root, p[1]};
    } else {
        TreeNode[] p = splitBST(root.left, V);
        root.left = p[1];
        return new TreeNode[]{p[0], root};
    }
}

vector<TreeNode*> splitBST(TreeNode* root, int V) {
    if (!root) return {nullptr, nullptr};
    if (root->val <= V) {
        auto p = splitBST(root->right, V);
        root->right = p[0];
        return {root, p[1]};
    } else {
        auto p = splitBST(root->left, V);
        root->left = p[1];
        return {p[0], root};
    }
}

Explanation

We need to cut a BST into two valid BSTs: one holding every key <= V and one holding every key > V. The trick is to use recursion and let the BST ordering do the heavy lifting.

Look at the current root. If root.val <= V, then the root and its entire left subtree belong to the small half. But its right subtree might mix small and large keys, so we recurse into root.right to split it, then reattach the small part back as root.right and bubble the large part up.

The other case is a mirror image. If root.val > V, the root and its right subtree go to the large half, and we recurse into root.left, reattaching the large part as root.left and passing the small part up.

Example: root=[4,2,6,1,3,5,7], V=2. At 4 (> 2) we go left; at 2 (<= 2) we keep it small and split its right child 3, which is > 2 and joins the large side under 4. The result is small [2,1] and large [4,3,6,5,7].

Each call moves one level down the tree, so the work is O(h) where h is the tree height.

Time: O(h) Space: O(h)