Introduction

Splitting a binary search tree means partitioning it into two valid BSTs around a pivot value. One resulting tree contains all keys less than or equal to the pivot, and the other contains all keys greater than the pivot.

The Core Recursive Idea

The BST property makes the split efficient because every comparison tells you which entire side of the tree belongs to which result.

Suppose you want to split around k:

• if root.val <= k, then the root belongs in the left result tree
• only the root's right subtree might still contain nodes that must be split
• if root.val > k, then the root belongs in the right result tree
• only the root's left subtree might still contain nodes that must be split

That leads to a natural recursive algorithm that returns two roots.

A Runnable Python Implementation

Here is a clean implementation that preserves the BST structure by rewiring child pointers during the recursion:

1from dataclasses import dataclass
2from typing import Optional, Tuple
3
4
5@dataclass
6class Node:
7    val: int
8    left: Optional["Node"] = None
9    right: Optional["Node"] = None
10
11
12def split_bst(root: Optional[Node], k: int) -> Tuple[Optional[Node], Optional[Node]]:
13    if root is None:
14        return None, None
15
16    if root.val <= k:
17        left_tree, right_tree = split_bst(root.right, k)
18        root.right = left_tree
19        return root, right_tree
20
21    left_tree, right_tree = split_bst(root.left, k)
22    root.left = right_tree
23    return left_tree, root

The important part is the pointer update after the recursive call:

• when root.val <= k, the left side of the split coming from root.right remains attached to root.right
• the right side of that split becomes the separate greater-than tree
• when root.val > k, the logic mirrors on the left subtree

This is easier to understand if you think in terms of "keep the part that still matches the root, detach the part that no longer does."

Why the Algorithm Works

Take the root.val <= k case. Every value in root.left is already less than or equal to root.val, so it also belongs in the left result tree. The only uncertainty is in root.right, because some nodes there may still be less than or equal to k while others may be greater.

After splitting root.right, you receive:

• a subtree whose values are still less than or equal to k
• a subtree whose values are greater than k

Attach the first one back to root.right, and return the second one as the right result tree.

The root.val > k case is the symmetric mirror image. By induction on subtree size, both returned trees remain valid BSTs.

Example Walkthrough

Consider this tree and split it at k = 4:

1        5
2       / \
3      3   8
4     / \   \
5    2   4   10

The result should be:

• left tree with 2, 3, and 4
• right tree with 5, 8, and 10

When the recursion starts at 5, the root is greater than 4, so 5 must belong to the right result. The algorithm then splits the left subtree rooted at 3. Since 3 <= 4, that node belongs to the left result, and only its right subtree needs further splitting. That eventually isolates 4 into the left result and reconnects the rest correctly.

The algorithm never scans irrelevant branches because the BST ordering already tells it where the uncertainty lives.

Complexity and Practical Uses

The running time is O(h), where h is the height of the tree, because the recursion follows one path down the tree and rewires pointers on the way back. In a balanced BST that is O(log n). In the worst case of a completely skewed tree, it becomes O(n).

This operation is useful in:

• treaps and other split-merge trees
• range query data structures
• persistent tree variants
• problems that need to partition keys efficiently

Even if you are not building an advanced balanced tree, split is a good example of how much work BST ordering can eliminate when you use it directly.

Common Pitfalls

The most common mistake is forgetting to reattach the subtree returned by the recursive call. If you split root.right and fail to assign the left part back into root.right, you lose nodes.

Another mistake is being inconsistent about the pivot rule. Decide whether nodes equal to k belong in the left or right result and implement that rule consistently. The code above uses "less than or equal to k" on the left side.

Developers also sometimes try to rebuild both trees from scratch, which is unnecessary. The recursive split works by reusing existing nodes and changing only a few pointers.

Summary

• Splitting a BST uses the ordering invariant to partition nodes around a pivot efficiently.
• The recursive algorithm returns two roots: one for keys less than or equal to k, and one for keys greater than k.
• Only one subtree needs recursive splitting at each step.
• Rewire child pointers carefully so nodes stay attached to the correct result tree.
• The time complexity is O(h), which is O(log n) for balanced trees.