Split BST - Solution & Explanation

Problem Overview: Given the root of a Binary Search Tree and a target value V, split the tree into two separate BSTs. The first tree contains all nodes with values <= V, and the second contains nodes with values > V. The relative structure of nodes must remain the same as in the original tree.

Approach 1: Inorder Traversal + Rebuild Trees (O(n) time, O(n) space)

The simplest way to reason about the split is to flatten the BST using an inorder traversal. Inorder traversal of a binary search tree produces a sorted sequence of values. Once you have the sorted array, iterate through it and separate values into two lists: values <= V and values > V. Then rebuild two BSTs from those arrays using standard sorted-array-to-BST construction.

This approach works because the BST property guarantees sorted order after traversal. The downside is that it discards the original structure and rebuilds trees from scratch, which requires O(n) additional memory. It’s useful as a conceptual baseline or when tree structure preservation is not required.

Approach 2: Recursive BST Split (O(n) time, O(h) space)

The optimal solution uses recursion and the ordering property of the tree. At each node, compare node.val with V. If node.val <= V, the node belongs to the left result tree. However, its right subtree may contain values greater than V, so recursively split the right subtree. Attach the returned "<= V" portion back as node.right, and return the current node as part of the first tree.

If node.val > V, the node belongs to the second tree. Its left subtree may contain values <= V, so recursively split the left subtree. Attach the returned "> V" portion back as node.left, and return the current node as part of the second tree.

This method preserves the original structure and only rewires pointers during recursion. Each node is processed once, giving O(n) time complexity. The recursion depth equals the tree height h, so the space complexity is O(h). This approach naturally fits problems involving recursion and BST structural manipulation.

Approach 3: Iterative Pointer Adjustment (O(n) time, O(h) space)

An iterative version simulates the recursive logic using a stack. Traverse the tree while maintaining two partial trees: one for nodes <= V and one for nodes > V. At each step, detach and reconnect subtrees depending on whether the current node falls on the left or right side of the split. This avoids recursive calls but still requires a stack proportional to the tree height.

The iterative method can be helpful in environments where recursion depth is limited. However, the logic becomes more verbose compared to the recursive approach, and interviewers typically expect the recursive BST split.

Recommended for interviews: The recursive BST split is the expected solution. It directly uses the BST ordering property and processes each node once. Showing the inorder rebuild approach demonstrates understanding, but implementing the recursive pointer split proves you can manipulate tree structure efficiently.