Split BST

Given the root of a binary search tree and an integer target, split the tree into two BSTs: one containing all values less than or equal to target, and the other containing all values greater than target. Pattern focus: BST Insert and Delete. The split uses the BST ordering to cut and reconnect only the necessary branches.

Input Format

root = binary tree root, target = split value

Output Format

JSON string with 'left' and 'right' tree serializations

Constraints

  • 0 <= number of nodes <= 10^5
  • -10^9 <= node values <= 10^9
  • root and target must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

root = [4,2,6,1,3,5,7]
target = 2

Output:

{"left":[2,1],"right":[4,3,6,5,7]}

Explanation:

Values <= 2 stay on the left; all larger values move to the right tree.

Example 2:

Input:

root = [6,2,8,0,4,7,9,null,null,3,5]
target = 5

Output:

{"left":[2,0,4,null,null,3,5],"right":[6,null,8,7,9]}

Explanation:

The split preserves BST structure on both sides.

Loading...
Split BST - Binary Search Tree DSA Problem