Solution: Split BST

Grokking the Art of Recursion for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Split BST

Table of Contents

Contents are not accessible

Problem Statement

Write a Recursive Approach to Split BST.

Given the root of a Binary Search Tree (BST) and an integer target, split the tree into two separate subtrees based on this target value.

The first subtree should contain all nodes with values less than or equal to the target.
The second subtree should contain all nodes with values greater than the target.

Even if the target value doesn't exist in the tree, the split should still happen based on the condition.

Important: The original parent-child relationships should be preserved as much as possible. That means if a node and its child both end up in the same subtree, they must still be connected in the same way as they were in the original tree.

Return an array of the two roots of the two subtrees in order.

Examples

Example 1:

Input:

Binary Search Tree:

Target: 5

Output:

Split BST 1:

Tree 1 (Greater):
```
      6
       \
        7
```
Tree 2 (Smaller):
```
     4
    / \
   2   5
  /
 1
  \
   3
```

Explanation:
- In this example, the binary search tree is split based on the target value of 5.
- All nodes greater than the target value (6, 7) are moved to Tree 1, while all nodes smaller than or equal to the target value (4, 2, 5, 1, 3) are moved to Tree 2.
- The resulting Tree 1 contains nodes greater than 5, while Tree 2 contains nodes smaller than or equal to 5.

Example 2:

Input:

Binary Search Tree:

Target: 3

Output:

Split BST 2:

Tree 1 (Greater):

Tree 2 (Smaller):
```
     2
    / \
   1   3
```

Explanation:
- In this example, the binary search tree is split based on the target value of 3.
- All nodes greater than the target value (4, 6, 7) are moved to Tree 1, while all nodes smaller than or equal to the target value (2, 1, 3) are moved to Tree 2.
- The resulting Tree 1 contains nodes greater than 3, while Tree 2 contains nodes smaller than or equal to 3.

Example 3:

Input:

Binary Search Tree:

Target: 7

Output:

Split BST 3:

Tree 1 (Greater):
```
      7
```
Tree 2 (Smaller):
```
     4
    / \
   2   6
  / \  
 1   3
```

Explanation:
- In this example, the binary search tree is split based on the target value of 7.
- Only the root node (7) is greater than the target value and is moved to Tree 1.
- The remaining nodes (4, 2, 6, 1, 3) are smaller than or equal to the target value and are moved to Tree 2.
- The resulting Tree 1 contains only the root node 7, while Tree 2 contains all other nodes from the original tree.

Constraints:

The number of nodes in the tree is in the range [1, 50].
0 <= Node.val, target <= 1000

Solution

To split the BST, we need to traverse the tree recursively and split it based on the target value. The base case occurs when the current node is null, in which case we return null for both subtrees. The recursive case involves comparing the value of the current node with the target value and splitting the tree accordingly.

If the current node's value is less than the target value, the entire left subtree is included in the resulting left subtree, and we need to split the right subtree recursively.
If the current node's value is greater than or equal to the target value, the entire right subtree is included in the resulting right subtree, and we need to split the left subtree recursively.

The algorithm's overall approach is as follows:

If the root is null, return null for both subtrees.
If the root's value is less than the target value, split the right subtree recursively.
If the root's value is greater than or equal to the target value, split the left subtree recursively.

The resulting subtrees are then connected to the appropriate sides of the root node, forming the split BST.

Code

Here is the code for this algorithm:

Python3

. . . .

Space and Time Complexity

The time complexity of this algorithm is $O(N)$ , where N is the number of nodes in the input BST. In the worst case, we need to traverse all nodes of the BST once to split it into two subtrees.

The space complexity is $O(N)$ as well, considering the recursive stack space used during the recursion. In the worst case, the recursion depth can be equal to the height of the BST, which is $O(N)$ for an unbalanced BST.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible