LeetCode 776 - Split BST

Difficulty: 🟡 Medium
Topics: Tree, Binary Search Tree, Recursion, Binary Tree

Solution

Problem Understanding

The problem asks us to split a binary search tree (BST) into two separate subtrees based on a target value. Specifically, the first subtree should contain all nodes with values less than or equal to the target, and the second subtree should contain all nodes with values strictly greater than the target. Importantly, the structure of each resulting subtree should preserve the original parent-child relationships where possible.

The input consists of a BST root and an integer target. The output is an array of two tree roots: the root of the subtree with values ≤ target and the root of the subtree with values > target. The BST property is critical because it ensures that for any node, all values in its left subtree are smaller and all values in its right subtree are larger, which allows efficient recursive splitting.

The constraints indicate the tree has at most 50 nodes and node values range from 0 to 1000. The small size means even simple recursive solutions are viable, but the BST structure suggests a recursive or divide-and-conquer approach will be cleaner and more efficient.

Important edge cases include:

The target is smaller than all nodes, so the left subtree is empty.
The target is larger than all nodes, so the right subtree is empty.
The tree contains only one node.
The tree does not contain the exact target value.

Approaches

A brute-force approach would involve performing an in-order traversal to collect all nodes, partitioning them based on the target, and then reconstructing two BSTs from the two sets. This works because in-order traversal of a BST produces a sorted array, but rebuilding a BST from a sorted array requires careful handling to maintain tree structure and is more work than necessary.

The optimal approach leverages the BST property recursively. For any node:

If node.val ≤ target, the node belongs to the left subtree. We recursively split its right child, attach the left part of that split as the node’s new right child, and return the node as the left subtree root.
If node.val > target, the node belongs to the right subtree. We recursively split its left child, attach the right part of that split as the node’s new left child, and return the node as the right subtree root.

This approach efficiently splits the tree in-place without additional storage or traversal.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Traverse tree to array, split array, rebuild two BSTs
Optimal	O(n)	O(h)	Recursive in-place split using BST properties, h = tree height

Algorithm Walkthrough

Start with the root node. Check its value relative to the target.
If root.val ≤ target:

This node belongs in the left subtree.
Recursively split the right child.
Attach the left result of that split as the new right child of the current node.
Return [current node, right result] as the split.

If root.val > target:

This node belongs in the right subtree.
Recursively split the left child.
Attach the right result of that split as the new left child of the current node.
Return [left result, current node] as the split.

Base case: if the node is null, return [None, None].

Why it works: The recursion guarantees that at every node, we place it correctly according to the BST property and the target. By recursively splitting children and updating pointers, we maintain the structure of each subtree while ensuring all values are correctly partitioned.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from typing import Optional, List

class Solution:
    def splitBST(self, root: Optional[TreeNode], target: int) -> List[Optional[TreeNode]]:
        if not root:
            return [None, None]
        
        if root.val <= target:
            left_subtree, right_subtree = self.splitBST(root.right, target)
            root.right = left_subtree
            return [root, right_subtree]
        else:
            left_subtree, right_subtree = self.splitBST(root.left, target)
            root.left = right_subtree
            return [left_subtree, root]

This implementation directly follows the algorithm. The recursion handles the splitting, and the reassignment of children ensures the original BST structure is maintained. If the node is null, it returns two null trees, correctly handling the edge case of an empty subtree.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func splitBST(root *TreeNode, target int) []*TreeNode {
    if root == nil {
        return []*TreeNode{nil, nil}
    }

    if root.Val <= target {
        split := splitBST(root.Right, target)
        root.Right = split[0]
        return []*TreeNode{root, split[1]}
    } else {
        split := splitBST(root.Left, target)
        root.Left = split[1]
        return []*TreeNode{split[0], root}
    }
}

The Go version mirrors the Python logic. We handle nil nodes as base cases, and slices are used to return two roots. Child reassignment ensures the original BST structure is preserved.

Worked Examples

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

Start at node 4 (4 > 2) → recurse on left subtree.
Node 2 (2 ≤ 2) → recurse on right child (node 3).
Node 3 (3 > 2) → recurse on left child (None) → return [None, None].
Node 3 attaches left child as None → returns [None, 3].
Node 2 attaches right child as None → returns [2, 3].
Node 4 attaches left child as 3 → final split: left [2,1], right [4,3,6,null,null,5,7].

Example 2: root = [1], target = 1

Node 1 (1 ≤ 1) → recurse on right child (None) → return [None, None].
Attach right child as None → return [1, None].

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited once in the recursion.
Space	O(h)	Recursion stack, where h is the tree height. Worst case h = n for skewed tree.

The recursive solution is efficient because it only visits each node once and performs constant work at each step. Space usage is dominated by the recursion stack, which is proportional to the height of the tree.

Test Cases

# Provided examples
assert Solution().splitBST(TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6, TreeNode(5), TreeNode(7))), 2)[0].val == 2  # left root
assert Solution().splitBST(TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6, TreeNode(5), TreeNode(7))), 2)[1].val == 4  # right root
assert Solution().splitBST(TreeNode(1), 1)[0].val == 1  # left root
assert Solution().splitBST(TreeNode(1), 1)[1] is None  # right root

# Edge cases
assert Solution().splitBST(TreeNode(10), 5)[0] is None  # target smaller than all nodes
assert Solution().splitBST(TreeNode(10), 5)[1].val == 10  # target smaller than all nodes
assert Solution().splitBST(TreeNode(10), 15)[0].val == 10  # target larger than all nodes
assert Solution().splitBST(TreeNode(10), 15)[1] is None  # target larger than all nodes

Test	Why
Examples from prompt	Validates normal behavior and correct split
Single-node tree	Ensures base case handling
Target smaller than all nodes	Tests empty left subtree
Target larger than all nodes	Tests empty right subtree

Edge Cases

Target smaller than all nodes: If the target is less than the smallest node, the left subtree must be empty. Our recursion correctly returns [None, root].

Target larger than all nodes: If the target is larger than the largest node, the right subtree must be empty. Our recursion returns [root, None], preserving all nodes in the left subtree.

Single-node tree: When the tree has only one node, the recursion base case handles it cleanly. If the node is ≤ target, the left subtree contains the node; if it is > target, the right subtree contains the node. This prevents any null pointer errors.