Solution Explanation: Splitting a BST

The problem requires splitting a Binary Search Tree (BST) into two subtrees based on a target value. All nodes with values less than or equal to the target should be in the first subtree, and all nodes with values greater than the target should be in the second. Crucially, the original tree's structure should be preserved within each subtree.

This can be efficiently solved using recursion. The core idea is to traverse the tree, and at each node, decide whether it belongs to the left or right subtree based on its value relative to the target. The recursive function dfs (or its equivalent in different languages) handles this elegantly.

Algorithm

1. Base Case: If the current node is null (empty), return an array containing two null values, representing empty left and right subtrees.

2. Recursive Step:

   • If the current node's value (root.val) is less than or equal to the target:
     • Recursively call dfs on the right subtree (root.right).
     • The result is an array [left, right], where left is the root of the left subtree of the right subtree (which may be null), and right is the root of the right subtree of the right subtree (which may also be null).
     • Set the current node's right child to left.
     • Return [root, right], as the current node becomes the root of the left subtree (<= target), and right remains the root of the right subtree (> target).
   • Otherwise (if root.val > target):
     • Recursively call dfs on the left subtree (root.left).
     • The result is an array [left, right].
     • Set the current node's left child to right.
     • Return [left, root], because the current node now becomes the root of the right subtree.

Time and Space Complexity

Time Complexity: O(N), where N is the number of nodes in the BST. This is because the recursive function visits each node exactly once.

Space Complexity: O(H), where H is the height of the BST. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N, resulting in O(N) space complexity. In the best case (a balanced tree), H is log₂(N), resulting in O(log N) space complexity.

Code Examples (with explanations)

The provided code examples in Python, Java, C++, Go, and JavaScript all follow the same recursive algorithm. Let's break down a representative example (Python):

class Solution:
    def splitBST(self, root, target):
        def dfs(root):
            if root is None:
                return [None, None]  # Base case: empty subtree
            if root.val <= target:
                l, r = dfs(root.right) # Recursive call on right subtree
                root.right = l         # Connect the left part of the right subtree back
                return [root, r]       # Current node is part of <= target subtree
            else:
                l, r = dfs(root.left)  # Recursive call on left subtree
                root.left = r          # Connect the right part of the left subtree back
                return [l, root]       # Current node is part of > target subtree
        return dfs(root)
 

The dfs function recursively processes each node. The key steps are:

• The base case handles empty subtrees.
• If the node's value is less than or equal to the target, it's part of the less-than-or-equal-to subtree, so the right subtree is recursively processed, and then the result is connected correctly.
• If the node's value is greater than the target, it's part of the greater-than subtree, and similar steps are performed on the left subtree.

The main function simply calls the recursive dfs function and returns the result. All other language versions implement this same algorithm with minor syntactic differences.