LeetCode: 776. Split BST

2026-03-05

Recursively split the BST by target and reconnect children so each resulting tree preserves original parent-child relations.

LeetCode: 776. Split BST

LeetCode: 776. Split BST

Summary

Split a BST into two subtrees.

One subtree contains all nodes with values less than or equal to target.
The other subtree contains all nodes with values greater than target.

We also need to preserve the original BST structure as much as possible. Formally, for any child c with parent p in the original tree, if they are both in the same subtree after the split, then node c should still have the parent p.

Approach

Recursion.

At each node:

  • If root.val > target, the current root belongs to the right subtree.
    • Recursively split root.left.
    • Attach the returned right part to root.left.
    • Return [left_part, root].
  • Otherwise, the current root belongs to the left subtree.
    • Recursively split root.right.
    • Attach the returned left part to root.right.
    • Return [root, right_part].

Function

In split(root, target):

  • If root is None, return [None, None].
  • If root.val > target:
    • left, right = split(root.left, target)
    • root.left = right
    • return [left, root]
  • Else:
    • left, right = split(root.right, target)
    • root.right = left
    • return [root, right]

Complexity

Time complexity: O(H), where H is the tree height.
If the tree is balanced, this is O(log N); in the worst case (skewed tree), it is O(N).
Space complexity: O(H) for recursion.

| Case | Time | Space | | ------------ | -------- | -------- | | General BST | O(H) | O(H) | | Balanced BST | O(log N) | O(log N) | | Worst case | O(N) | O(N) |