Problem statement
Split a binary search tree into two trees: all values ≤target in the first, and all values >target in the second. Return their roots in that order. The target does not need to exist.
The original takeUforward prompt also requires preserving an original parent-child relation whenever both nodes belong to the same result. Do not just rebuild balanced trees from sorted values.
Its stated constraints are 1–50 nodes and values/target in 0–1000. The explanation assumes the standard strict BST ordering; the algorithm also works with consistent duplicate placement under a compatible ordering rule.
For level-order [4,2,6,1,3,5,7], target=2, the small tree is rooted at 2 with left child 1. The large tree is rooted at 4, with left child 3 and the original right subtree rooted at 6.
Constraints & requirements
- CONTRACT
- Preserve node identities and original edges whose endpoints stay on the same side.
Examples 3 test cases
Example 1 Case 1
- Input
insert=[4,2,6,1,3,5,7]; target=2- Output
Roots: 2, 4; inorder: [1, 2] | [3, 4, 5, 6, 7]
Also verify original 6→5 and 6→7 edges.
Example 2 Case 2
- Input
insert=[5]; target=5- Output
Roots: 5, null; inorder: [5] | []
Equality belongs to the small side.
Example 3 Case 3
- Input
insert=[5,2,8]; target=1- Output
Roots: null, 5; inorder: [] | [2, 5, 8]
An empty side is allowed.
Hints Optional
01Find the smaller problem
BST ordering classifies one whole child subtree immediately.
02Define the state
Return a pair: the ≤target root and the >target root. Split only the child that might cross the boundary.
03Connect the recurrence
For a small root, reattach the small right piece; for a large root, reattach the large left piece. Preserve the untouched child.
How to think before coding
Use the BST ordering before touching links. If root≤target, its entire left subtree already belongs to the small result; only the right child can cross the boundary. Split that child and reconnect the returned small part. The root>target case is symmetric. Each call returns TWO roots, and only the original boundary-path edges are changed.
Baseline—and why sorted rebuilding is insufficient
An inorder traversal collects sorted values in O(n) time. Partitioning them by target and building two new BSTs is easy, but it changes identities and can destroy a required edge such as original 6→5 even though both belong to the large tree. It is therefore not a valid solution to this exact contract.
A valid whole-tree baseline can recursively split both children and combine their same-side pieces:
static RecursionProblemExamples.TreeNode[] splitBoth(RecursionProblemExamples.TreeNode root, int target) {
if (root == null) return new RecursionProblemExamples.TreeNode[]{null, null}; // Empty halves.
var left = splitBoth(root.left, target); // Visit all left descendants, even homogeneous ones.
var right = splitBoth(root.right, target); // Visit all right descendants too.
if (root.val <= target) { // Ordering guarantees left[1] is empty.
root.left = left[0]; // Keep the small left subtree under its original parent.
root.right = right[0]; // Reconnect the small part from the right.
return new RecursionProblemExamples.TreeNode[]{root, right[1]}; // Pass the large piece upward.
}
root.left = left[1]; // Reconnect the large part from the left.
root.right = right[1]; // Ordering guarantees right[0] is empty.
return new RecursionProblemExamples.TreeNode[]{left[0], root}; // Return small then large.
}That takes O(n) time and O(h) peak stack space. The improved method avoids visiting the child that ordering already classifies.
Intuition: only one child can cross the boundary
If root.val≤target, the whole left subtree is also ≤target. Leave it alone. Only the right subtree might contain a mixture.
If root.val>target, the whole right subtree is also >target. Leave it alone. Only the left subtree needs splitting.
The recursive promise is: return [smallRoot, largeRoot] for this subtree, preserving same-side original edges. That promise is more informative than returning a single root.
Boundary-path recursive solution
Use the judge’s TreeNode type in submissions. The companion provides a small local node class for tests.
public static TreeNode[] splitBst(TreeNode root, int target) {
if (root == null) return new TreeNode[] {null, null}; // Two empty pieces split an empty subtree.
if (root.val <= target) { // Root and its entire left subtree belong to the small result.
TreeNode[] parts = splitBst(root.right, target); // Only the right subtree can straddle target.
root.right = parts[0]; // Reattach its small piece; left remains untouched.
return new TreeNode[] {root, parts[1]}; // Root is small; pass the large piece upward.
}
TreeNode[] parts = splitBst(root.left, target); // Root is large; only its left can straddle target.
root.left = parts[1]; // Reattach the large left piece; right remains untouched.
return new TreeNode[] {parts[0], root}; // Small piece comes first in the result contract.
}Why assign root.right=parts[0] in the small-root case? parts[0] is precisely the portion of the original right subtree that still belongs beside root. parts[1] must be separated and returned as the large result.
The large-root case is the mirror: attach parts[1] on the left, return parts[0] separately. Do not swap the pair’s meanings when returning upward.
Mistakes, tests, and junior-engineer doubts
- Rebuilding sorted trees can violate the required parent-child preservation.
- Recursing into both children misses the O(h) optimization.
- Using < instead of ≤ puts an equal target on the wrong side.
- Confusing parts[0] with parts[1] reconnects the wrong tree.
- target below the minimum → empty small tree; above the maximum → empty large tree.
- Empty-tree extension → [null,null]; single node=5,target=5 → [node,null].
- Target=2 in [4,2,6,1,3,5,7] must preserve 6→5 and 6→7.
- Validate identities, ordering, partition membership, disjointness, and preserved same-side edges—not only inorder values.
Input tree, call chain, and returned trees
Original: 4
/ \
2 6
/ \ / \
1 3 5 7
split(4,2): root large → split left
└─ split(2,2): root small → split right
└─ split(3,2): root large → split left
└─ split(null,2) returns [null,null]
3.left=null; returns [null,3]
2.right=null; returns [2,3]
4.left=3; returns [2,4]
Small: 2 Large: 4
/ / \
1 3 6
/ \
5 7The recursion tree is a single boundary path, not a traversal of every tree node. Input-tree branching and call-tree branching are different concepts.
Dry run: each reconnect has a reason

Read the text transcript
| Returning frame | Child pair | Pointer update | Returned pair |
|---|---|---|---|
| null | none | none | [null,null] |
| 3 (>2) | [null,null] | 3.left=null | [null,3] |
| 2 (≤2) | [null,3] | 2.right=null | [2,3] |
| 4 (>2) | [2,3] | 4.left=3 | [2,4] |
Compare the call chain with both returned trees after each reconnect. A missing target is fine: comparisons still define the boundary.
Why this is correct
In the small-root case, BST ordering classifies root and its entire left subtree as small. By induction, splitting the right returns exactly its small and large portions. Attaching the small portion as root.right preserves the BST property; passing the large portion upward separates all remaining values. Only boundary-crossing edges are cut. Original edges whose endpoints stay on the same side are retained. The large-root case is symmetric.
Every node belongs to exactly one result; no node is copied, lost, shared between results, or introduced twice.
Complexity and mutation
O(h) time and O(h) auxiliary call-stack space, where h is tree height. Only one path is visited. A balanced tree has h=O(log n); a skewed tree can have h=O(n). Do not claim logarithmic time for an arbitrary BST.
This implementation intentionally mutates child pointers and reuses the original nodes. If a caller needs an immutable original tree, copying is a different contract with different memory cost.
Recognition and related practice
“BST + threshold + preserve structure” suggests subtree ordering and a returned pair. Compare immutable-list printing: both depend on what a child promises, but only this algorithm changes pointers.
Company evidence
Salesforce · historical candidate report. A Hyderabad MTS experience posted in October 2020 reports splitting a BST by a given value in round two. The post does not reproduce every structure-preservation detail, so the badge indicates a reported split-BST question, not verified identical judge constraints or current interview frequency. Checked 3 October 2026.
Final takeaway
Keep the homogeneous side untouched. Split the boundary side, reconnect the appropriate piece, and return two roots in a consistent order.
Download all tested Java solutions. These methods use Java 17+; import java.util.* in a standalone program. Use the Java comments and static dry run together to follow each call, return and update.
Practice next
Next lessonReverse a Stack in Java: Understand Every Call and ReturnCompare a different recursive promise and how its parent resumes.