Problem Description

You're given a binary search tree (BST) and an integer target. Your task is to split the tree into two separate subtrees based on the target value:

1. First subtree: Contains all nodes with values less than or equal to target
2. Second subtree: Contains all nodes with values greater than target

The key requirement is to preserve the original parent-child relationships as much as possible. This means if two nodes (parent and child) from the original tree end up in the same subtree after splitting, they should maintain their parent-child relationship.

The tree might not contain a node with the exact target value - you're simply using it as a threshold for splitting.

Example walkthrough:

If you have a BST and target = 4:

• All nodes with values ≤ 4 go to the first tree
• All nodes with values > 4 go to the second tree
• The BST property is maintained in both resulting trees

The solution uses a recursive approach that traverses the tree and makes decisions at each node:

• If root.val <= target: This node belongs to the left (smaller) tree. We recursively split the right subtree since it might contain both smaller and larger values. The left part of the split becomes the new right child of the current node.

• If root.val > target: This node belongs to the right (larger) tree. We recursively split the left subtree since it might contain both smaller and larger values. The right part of the split becomes the new left child of the current node.

The function returns an array [left_tree_root, right_tree_root] where:

• left_tree_root is the root of the tree with all values ≤ target
• right_tree_root is the root of the tree with all values > target

Intuition

The key insight comes from understanding the BST property: for any node, all values in its left subtree are smaller, and all values in its right subtree are larger.

When we encounter a node, we need to decide which resulting tree it belongs to based on comparing its value with target. But here's the crucial observation: the decision we make at each node affects how we handle its subtrees.

Let's think through the scenarios:

Case 1: Current node value ≤ target

• This node definitely belongs to the "smaller" tree
• Its entire left subtree also belongs to the "smaller" tree (BST property guarantees all left values are even smaller)
• But its right subtree is interesting - it might contain both values ≤ target and values > target
• So we need to recursively split the right subtree

Case 2: Current node value > target

• This node definitely belongs to the "larger" tree
• Its entire right subtree also belongs to the "larger" tree (BST property guarantees all right values are even larger)
• But its left subtree might contain both values ≤ target and values > target
• So we need to recursively split the left subtree

The elegance of the solution emerges from this pattern: when we split a subtree recursively, we get back two parts [l, r]. We then "stitch" the appropriate part back to maintain valid BST structure:

• If current node goes to the smaller tree (root.val <= target), we attach the smaller part of the split right subtree as our new right child
• If current node goes to the larger tree (root.val > target), we attach the larger part of the split left subtree as our new left child

This recursive approach naturally preserves the parent-child relationships because we're only modifying connections where nodes need to be separated into different trees. Nodes that stay together maintain their original structure.

Learn more about Tree, Binary Search Tree, Recursion and Binary Tree patterns.

Solution Approach

The solution implements a recursive depth-first search (DFS) approach to split the BST. Let's walk through the implementation step by step:

Base Case:

if root is None:
    return [None, None]

When we reach a null node, we return [None, None] indicating empty trees for both splits.

Recursive Logic:

The function examines each node and makes a decision based on comparing root.val with target:

When root.val <= target:

l, r = dfs(root.right)
root.right = l
return [root, r]

• The current node belongs to the "smaller or equal" tree
• We recursively split the right subtree by calling dfs(root.right)
• This returns [l, r] where l contains nodes ≤ target and r contains nodes > target
• We attach l as the new right child of the current node (replacing the original right subtree)
• We return [root, r] where root is now the root of the smaller tree, and r is the root of the larger tree from the split

When root.val > target:

l, r = dfs(root.left)
root.left = r
return [l, root]

• The current node belongs to the "greater than" tree
• We recursively split the left subtree by calling dfs(root.left)
• This returns [l, r] where l contains nodes ≤ target and r contains nodes > target
• We attach r as the new left child of the current node (replacing the original left subtree)
• We return [l, root] where l is the root of the smaller tree from the split, and root is now the root of the larger tree

Pattern Recognition:

This solution follows the "divide and conquer" pattern where:

1. We make a local decision at each node
2. Recursively solve subproblems (splitting subtrees)
3. Combine the results by adjusting pointers

The algorithm modifies the tree in-place, reusing existing nodes rather than creating new ones. This is efficient in terms of space complexity.

Time Complexity: O(n) where n is the number of nodes, as we visit each node exactly once.

Space Complexity: O(h) where h is the height of the tree, due to the recursive call stack. In the worst case (skewed tree), this could be O(n).

Example Walkthrough

Let's walk through splitting a BST with target = 4:

Original BST:        Target = 4
      5
     / \
    3   7
   / \   \
  2   4   8

Step-by-step execution:

1. Start at root (5): Since 5 > 4, this node belongs to the "greater" tree. We need to split its left subtree.

   • Recursively call dfs(node 3)

2. At node 3: Since 3 ≤ 4, this node belongs to the "smaller or equal" tree. We need to split its right subtree.

   • Recursively call dfs(node 4)

3. At node 4: Since 4 ≤ 4, this node belongs to the "smaller or equal" tree. Both children are null, so we recursively get [None, None] from the right subtree.

   • Set node4.right = None (no change)
   • Return [node4, None]

4. Back at node 3: We get [node4, None] from splitting the right subtree.

   • Set node3.right = node4 (maintaining the connection)
   • Return [node3, None] (entire subtree rooted at 3 goes to smaller tree)

5. Back at root (5): We get [node3, None] from splitting the left subtree.

   • Set node5.left = None (disconnect from smaller tree)
   • Return [node3, node5]

Result:

Smaller/Equal Tree (≤4):    Greater Tree (>4):
      3                           5
     / \                           \
    2   4                           7
                                     \
                                      8

The algorithm correctly:

• Kept nodes 2, 3, 4 together in the smaller tree (all ≤ 4)
• Kept nodes 5, 7, 8 together in the greater tree (all > 4)
• Preserved parent-child relationships where nodes stayed in the same tree
• Maintained BST property in both resulting trees

Solution Implementation

Time and Space Complexity

Time Complexity: O(h) where h is the height of the BST. In the worst case of a skewed tree, this becomes O(n) where n is the number of nodes.

The algorithm performs a single traversal from the root down to a leaf, following only one path through the tree. At each node visited, it performs constant time operations (comparisons and pointer reassignments). Since BST properties guide the traversal to follow either the left or right subtree (never both), the maximum number of nodes visited equals the height of the tree.

Space Complexity: O(h) where h is the height of the BST. In the worst case of a skewed tree, this becomes O(n).

The space complexity comes from the recursive call stack. The maximum depth of recursion equals the height of the tree, as the algorithm follows a single path from root to leaf. Each recursive call adds a frame to the call stack with constant space for local variables l and r. No additional data structures are used, and the tree modification is done in-place by adjusting pointers.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Assigning Split Results

One of the most common mistakes is confusing which part of the split result to attach to the current node. When splitting a subtree, developers often mix up the assignment logic.

Incorrect Implementation:

if node.val <= target:
    left_split, right_split = dfs(node.right)
    node.right = right_split  # WRONG! Should be left_split
    return [node, left_split]  # WRONG! Should be [node, right_split]

Why this happens: It's counterintuitive that when the current node belongs to the "smaller" tree and we split its right subtree, we keep the "smaller" part of that split (left_split) attached to it.

Correct Logic:

• When node.val <= target: The node stays in the smaller tree, so we need to keep only the nodes from its right subtree that are also ≤ target (which is left_split)
• When node.val > target: The node stays in the larger tree, so we need to keep only the nodes from its left subtree that are also > target (which is right_split)

2. Modifying the Original Tree Without Creating a Copy

The current solution modifies the original tree in-place. If you need to preserve the original tree structure, you'll run into issues.

Problem Scenario:

# Original tree is modified after splitting
original_root = create_bst()
result = splitBST(original_root, 5)
# original_root is now corrupted and no longer represents the original tree

Solution - Create New Nodes:

def splitBST(self, root: Optional[TreeNode], target: int) -> List[Optional[TreeNode]]:
    def dfs(node: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        if node is None:
            return [None, None]
      
        # Create a copy of the current node
        node_copy = TreeNode(node.val)
      
        if node.val <= target:
            left_split, right_split = dfs(node.right)
            # Copy the left subtree reference
            node_copy.left = node.left
            node_copy.right = left_split
            return [node_copy, right_split]
        else:
            left_split, right_split = dfs(node.left)
            node_copy.left = right_split
            # Copy the right subtree reference
            node_copy.right = node.right
            return [left_split, node_copy]
  
    return dfs(root)

3. Handling Edge Cases Incorrectly

Developers sometimes forget to handle special cases properly:

Missing Edge Case Handling:

def splitBST(self, root: Optional[TreeNode], target: int) -> List[Optional[TreeNode]]:
    # Forgetting to handle None root
    if root.val <= target:  # This will crash if root is None
        # ... rest of code

Proper Edge Case Handling:

• Always check for None nodes first
• Consider trees with single nodes
• Handle cases where all nodes are either ≤ target or all > target

4. Confusion About BST Properties After Split

Some developers worry about maintaining BST properties and try to rebalance or resort nodes unnecessarily.

Key Understanding: The split operation naturally maintains BST properties because:

• We're only breaking parent-child links between nodes that belong to different groups
• Within each group, the relative ordering is preserved
• No node values are changed, only tree structure is modified

The algorithm guarantees both resulting trees remain valid BSTs without any additional balancing or sorting operations.