Knowledge Guide
Home › DSA › Recursion

Solution Split BST

Problem Statement

Write a Recursive Approach to Split BST.

Given the root of a Binary Search Tree (BST) and an integer target, split the tree into two separate subtrees based on this target value.

Even if the target value doesn't exist in the tree, the split should still happen based on the condition.

Important: The original parent-child relationships should be preserved as much as possible. That means if a node and its child both end up in the same subtree, they must still be connected in the same way as they were in the original tree.

Return an array of the two roots of the two subtrees in order.

Examples

Example 1:

Example 2:

Example 3:

Constraints:

Solution

To split the BST, we need to traverse the tree recursively and split it based on the target value. The base case occurs when the current node is null, in which case we return null for both subtrees. The recursive case involves comparing the value of the current node with the target value and splitting the tree accordingly.

  1. If the current node's value is less than the target value, the entire left subtree is included in the resulting left subtree, and we need to split the right subtree recursively.
  2. If the current node's value is greater than or equal to the target value, the entire right subtree is included in the resulting right subtree, and we need to split the left subtree recursively.

The algorithm's overall approach is as follows:

The resulting subtrees are then connected to the appropriate sides of the root node, forming the split BST.

Image
Image

Code

Here is the code for this algorithm:

java
// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;

//     TreeNode(int val) {
//         this.val = val;
//     }
// }

public class Solution {

  public static TreeNode[] splitBST(TreeNode root, int target) {
    if (root == null) {
      return new TreeNode[] { null, null }; // Base case: empty subtree
    }

    if (root.val <= target) {
      TreeNode[] rightSplit = splitBST(root.right, target); // Split right subtree recursively
      root.right = rightSplit[0]; // Connect the resulting right subtree to the current node's right
      return new TreeNode[] { root, rightSplit[1] }; // Return root and right subtree
    } else {
      TreeNode[] leftSplit = splitBST(root.left, target); // Split left subtree recursively
      root.left = leftSplit[1]; // Connect the resulting left subtree to the current node's left
      return new TreeNode[] { leftSplit[0], root }; // Return left subtree and root
    }
  }

  public static void main(String[] args) {
    // Example inputs
    TreeNode root1 = new TreeNode(4);
    root1.left = new TreeNode(2);
    root1.right = new TreeNode(6);
    root1.left.left = new TreeNode(1);
    root1.left.right = new TreeNode(3);
    root1.right.right = new TreeNode(7);
    int target1 = 5;

    TreeNode root2 = new TreeNode(3);
    root2.left = new TreeNode(2);
    root2.right = new TreeNode(4);
    int target2 = 4;

    TreeNode root3 = new TreeNode(2);
    root3.left = new TreeNode(1);
    root3.right = new TreeNode(3);
    int target3 = 1;

    // Split BSTs
    TreeNode[] split1 = splitBST(root1, target1);
    TreeNode[] split2 = splitBST(root2, target2);
    TreeNode[] split3 = splitBST(root3, target3);

    // Print results
    System.out.println(
      "Split BST 1: " + printBST(split1[0]) + ", " + printBST(split1[1])
    );
    System.out.println(
      "Split BST 2: " + printBST(split2[0]) + ", " + printBST(split2[1])
    );
    System.out.println(
      "Split BST 3: " + printBST(split3[0]) + ", " + printBST(split3[1])
    );
  }

  // Helper method to print the BST
  public static String printBST(TreeNode root) {
    if (root == null) {
      return "";
    }
    String left = printBST(root.left);
    String right = printBST(root.right);
    return left + " " + root.val + " " + right;
  }
}

Space and Time Complexity

The time complexity of this algorithm is , where N is the number of nodes in the input BST. In the worst case, we need to traverse all nodes of the BST once to split it into two subtrees.

The space complexity is as well, considering the recursive stack space used during the recursion. In the worst case, the recursion depth can be equal to the height of the BST, which is for an unbalanced BST.

🤖 Don't fully get this? Learn it with Claude

Stuck on Solution Split BST? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Solution Split BST** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Solution Split BST** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Solution Split BST**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Solution Split BST**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Solution Good NumberSolution Powx,n →