18. Split BST

Grokking the Art of Recursion for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

18. 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.

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

Constraints:

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

Try it yourself

Try solving this question here:

Python3

. . . .

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible