Split BST

Split BST

What is this problem about?

The Split BST coding problem involves taking a Binary Search Tree (BST) and a target value. You need to split the tree into two separate subtrees: one containing all nodes with values less than or equal to the target, and the other containing all nodes with values greater than the target. The original structure of the tree should be maintained as much as possible, and both resulting subtrees must still satisfy the BST property.

Why is this asked in interviews?

This problem is common in Amazon and Coupang interviews because it tests a candidate's mastery of recursion and their understanding of tree properties. Unlike simple traversals, this problem requires you to modify tree pointers and return multiple values (the roots of the two new subtrees). It's an excellent test of your mental model of how recursive calls return and how they can be used to build or modify complex data structures.

Algorithmic pattern used

The Algorithmic pattern used here is Recursion on a Tree. Since it's a BST, we can use the property that left is smaller and right is larger to decide which way to go. If the current node's value is $\le$ target, then the current node and its entire left subtree belong to the "smaller" group. However, some nodes in its right subtree might also be $\le$ target. We recursively split the right child. The part of the right child that is $\le$ target becomes the new right child of our current node, and the part that is $>$ target is returned as the root of the "larger" tree.

Example explanation (use your own example)

Imagine a BST with root 4, left child 2, and right child 6. Target is 3.

1. We look at 4. 4 > 3, so 4 and its right child (6) belong to the "larger" tree.
2. We need to split 4's left child (2).
3. We look at 2. 2 $\le$ 3, so 2 and its left child (if it had one) belong to the "smaller" tree.
4. We need to split 2's right child (currently empty).
5. The split of 2's right child returns [null, null].
6. 2's new right child becomes null.
7. 2 is returned as the root of the "smaller" tree.
8. Back at 4, its new left child becomes the "larger" part of the split of its original left child (which is null in this simple case).
9. The final result is two trees: one rooted at 2 and one rooted at 4 (with right child 6).

Common mistakes candidates make

• Losing nodes: Forgetting to re-attach the results of the recursive calls to the correct parent.
• Incorrect BST property: Failing to realize that a split might happen deep within a subtree, not just at the root.
• Returning only one root: The problem requires returning two roots, so you must use an array, a pair, or an object to hold both.
• Base case errors: Not handling the null node correctly, which is the natural stopping point for the recursion.

Interview preparation tip

To excel at Recursion, Binary Search Tree, Binary Tree, Tree interview pattern problems, practice drawing out the tree on a whiteboard. Trace the recursive calls and see how the pointers change at each step. Understanding how the "return" value of a function can be used to update the "current" node's children is key to solving tree mutation problems.