776. Split BST

MediumTreeBinary Search TreeRecursionBinary Tree

Problem Description

Given a Binary Search Tree (BST) and an integer target, the problem asks us to split the tree into two separate subtrees based on the values relative to target. The first subtree should contain all the nodes that have values less than or equal to the target, and the second subtree should contain all the nodes that have values greater than the target. It's important that if a node was a parent to another node before the split, and both of them ended up in the same subtree after the split, then their parent-child relationship should remain unchanged.

Intuition

The intuition for solving this problem lies in understanding the properties of a BST. In a BST, for any given node, all the values in its left subtree are less than its value, and all the values in its right subtree are greater than its value. With this characteristic in mind, when we come across a node that is less than or equal to the target, we know that this node and its left subtree should definitely be a part of the subtree that contains nodes less than or equal to the target. However, we need to recursively adjust its right subtree to split it further according to the target.

Similarly, if a node's value is greater than the target, this node and its right subtree should be in the subtree that contains nodes greater than the target. Here, the left subtree must be checked recursively to separate the nodes correctly.

The recursive approach involves visiting each node and deciding whether to split its left or right subtree (or both), thereby constructing the two subtrees required while maintaining the original parent-child relationship whenever possible. The recursion eventually hits a base case when it reaches a null node, at which point it returns a pair of null nodes representing the end of a branch.

Hence, for each node, we return a pair: the first element of the pair is the root of the subtree containing nodes less than or equal to the target, and the second element is the root of the subtree containing nodes greater than the target.

Learn more about Tree, Binary Search Tree, Recursion and Binary Tree patterns.

Solution Approach

The solution implements a depth-first search (DFS) algorithm through a recursive function called dfs. This function takes a node of the tree as an input and splits it into two subtrees according to the target. dfs returns a list with two elements, where the first element is the root of the subtree with nodes less than or equal to the target, and the second is the root of the subtree with nodes greater than the target.

Here's a step-by-step breakdown of the dfs function in detail:

When the dfs function encounters a None node (the base case), it returns a pair of None nodes, indicating the end of a branch. This is represented by return [None, None].
If the current node's value is less than or equal to the target, all nodes in its left subtree are guaranteed to also be less than or equal to the target (by the BST property). The function proceeds to split the right subtree. The recursive call dfs(root.right) will split the right subtree into two parts: those less than or equal to the target (l) and those greater than the target (r). Since the current node and its left subtree are all less than or equal to the target, the current node's right child should be updated to l (the part of the right subtree that's less than or equal to the target). It then returns [root, r], where root is now the root of the subtree with data less than or equal to the target and r is the root of the subtree with data greater than the target.
If the current node's value is greater than the target, then by the BST property, all nodes in its right subtree are greater than the target. The function then recursively splits the left subtree with dfs(root.left). It receives a pair of roots, l for the left split (all nodes less than or equal to the target) and r for the right split (all nodes greater than the target up to now). In this case, root.left should be updated to r (the part of the left subtree that's greater than the target). The function then returns [l, root] as the nodes that are less than or equal to the target are now in l, and those that are greater than the target are under root.

As the recursion unwinds, each node processes its left or right subtrees depending upon its value relative to the target. Since recursion visits all nodes once, the time complexity is O(n), where n is the number of nodes in the BST. No extra space is used apart from the recursion stack, making the space complexity O(h), where h is the height of the BST.

The main function splitBST simply starts this recursive process by calling dfs on the root of the tree and then returns the result. The returned value is a list that holds the two new roots of the subtrees that are the result of the split.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider the following Binary Search Tree and the target value 3:

Our task is to split this BST into two subtrees, where the first subtree contains all nodes with values less than or equal to 3, and the second subtree contains all nodes with values greater than 3.

Let's apply the solution approach:

We begin with the root node (4). Since 4 is greater than 3, we'll need to split its left subtree to determine which nodes are less than or equal to the target, and the right subtree is already greater than 3.
Now we look at the left subtree:
```
    2
   / \
  1   3
```
The root here is 2, which is less than or equal to 3. So, we keep 2 and its left subtree as is because all values must also be less than or equal to 3. The right child of 2 is 3, which is equal to the target, so it too remains in the subtree. The right subtree of this node is processed, but since it's a leaf node (3), it is just included without changes. So no further action is needed, and we keep the left subtree as it is.
Returning to the original root node (4), we have already verified that its entire left subtree is less than or equal to the target. We can simply include this left subtree in our result. For the right subtree, which starts with the root node (4), we don't need to process it since it is already in the subtree that contains nodes greater than the target. So, we attach the original right subtree (starting with node 6) to our node 4.

The resulting subtrees are:

Subtree less than or equal to 3:
    2
   / \
  1   3

Subtree greater than 3:
    4
     \
      6
     / \
    5   7

The final output of the splitBST function would be the roots of the two subtrees: [2, 4]. Node 2 is the root of the subtree with nodes less than or equal to 3, and node 4 is the root of the subtree with nodes greater than 3.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def splitBST(self, root: Optional[TreeNode], target: int) -> List[Optional[TreeNode]]:
10        # Helper function to recursively split the BST
11        def dfs(node: Optional[TreeNode]) -> List[Optional[TreeNode]]:
12            # Base case: if the current node is None, return a pair of None nodes
13            if node is None:
14                return [None, None]
15          
16            # If current node's value is less than or equal to the target,
17            # split the right subtree
18            if node.val <= target:
19                left_of_right, right_of_right = dfs(node.right)
20                # Link the left part of the split right subtree to the current node's right
21                node.right = left_of_right
22                # The current node becomes part of the left tree, the right part
23                # of the split right subtree becomes the right tree
24                return [node, right_of_right]
25            else:
26                # If current node's value is greater than the target,
27                # split the left subtree
28                left_of_left, right_of_left = dfs(node.left)
29                # Link the right part of the split left subtree to the current node's left
30                node.left = right_of_left
31                # The left part of the split left subtree becomes the left tree,
32                # the current node becomes part of the right tree
33                return [left_of_left, node]
34
35        # Call the helper function with the root of the BST
36        return dfs(root)
37

1class Solution {
2    private int targetValue;
3
4    // Splits a BST into two trees based on the target value; each tree contains either all elements less than or equal to the target
5    // or all elements greater than the target, maintaining the BST properties.
6    public TreeNode[] splitBST(TreeNode root, int target) {
7        targetValue = target;
8        return split(root);
9    }
10
11    // A recursive helper function that splits the BST.
12    private TreeNode[] split(TreeNode node) {
13        if (node == null) {
14            return new TreeNode[]{null, null};
15        }
16        if (node.val <= targetValue) {
17            // If the current node's value is less than or equal to the target, split the right subtree.
18            TreeNode[] splitRight = split(node.right);
19            node.right = splitRight[0]; // The left part of the right subtree becomes the right child of the current node.
20            splitRight[0] = node; // The current node becomes the rightmost node of the left split tree.
21            return splitRight;
22        } else {
23            // If the current node's value is greater than the target, split the left subtree.
24            TreeNode[] splitLeft = split(node.left);
25            node.left = splitLeft[1]; // The right part of the left subtree becomes the left child of the current node.
26            splitLeft[1] = node; // The current node becomes the leftmost node of the right split tree.
27            return splitLeft;
28        }
29    }
30
31    // Definition for a binary tree node.
32    public class TreeNode {
33        int val;
34        TreeNode left;
35        TreeNode right;
36
37        TreeNode() {}
38
39        TreeNode(int val) {
40            this.val = val;
41        }
42
43        TreeNode(int val, TreeNode left, TreeNode right) {
44            this.val = val;
45            this.left = left;
46            this.right = right;
47        }
48    }
49}
50

1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    int targetValue;
16
17    // Splits the tree into two subtrees where one tree contains all elements less than or equal to target
18    // and the other contains all elements greater than target.
19    vector<TreeNode*> splitBST(TreeNode* root, int target) {
20        targetValue = target;
21        return split(root);
22    }
23
24    // Helper function to perform the split operation
25    vector<TreeNode*> split(TreeNode* rootNode) {
26        // If the current node is null, then return a pair of null pointers.
27        if (!rootNode) {
28            return {nullptr, nullptr};
29        }
30
31        // If the current node's value is less than or equal to the target, we process the right subtree.
32        if (rootNode->val <= targetValue) {
33            // Recursively split the right subtree.
34            vector<TreeNode*> ans = split(rootNode->right);
35
36            // Attach the 'less than or equal to target' part of the right subtree to the current node's right child.
37            rootNode->right = ans[0];
38
39            // The current node becomes part of the 'less than or equal to target' subtree.
40            ans[0] = rootNode;
41
42            // Return the updated pair of subtrees.
43            return ans;
44        } else {
45            // If the current node's value is greater than the target, process the left subtree.
46            vector<TreeNode*> ans = split(rootNode->left);
47
48            // Attach the 'greater than target' part of the left subtree to the current node's left child.
49            rootNode->left = ans[1];
50
51            // The current node becomes part of the 'greater than target' subtree.
52            ans[1] = rootNode;
53
54            // Return the updated pair of subtrees.
55            return ans;
56        }
57    }
58};
59

1// Typing definition for a binary tree node
2interface TreeNode {
3  val: number;
4  left: TreeNode | null;
5  right: TreeNode | null;
6}
7
8/**
9 * Splits a BST into two trees based on a target value
10 * @param {TreeNode | null} root - The root of the BST to split
11 * @param {number} target - The value to split the BST around
12 * @return {TreeNode[]} An array containing two trees: one with all values <= target, one with all values > target
13 */
14const splitBST = (root: TreeNode | null, target: number): [TreeNode | null, TreeNode | null] => {
15    // Initialized answer array where first element is the tree with values <= target,
16    // and second element is the tree with values > target.
17    let answer: [TreeNode | null, TreeNode | null] = [null, null];
18  
19    // If the root is null, return the answer array with both elements as null.
20    if (!root) {
21        return answer;
22    }
23
24    if (root.val <= target) {
25        // If root value is less than or equal to target, split the right subtree.
26        answer = splitBST(root.right, target);
27
28        // Attach the left part of the split right subtree to the current root's right.
29        root.right = answer[0];
30
31        // Set the current root as the new root for the left part.
32        answer[0] = root;
33    } else {
34        // If root value is greater than the target, split the left subtree.
35        answer = splitBST(root.left, target);
36
37        // Attach the right part of the split left subtree to the current root's left.
38        root.left = answer[1];
39
40        // Set the current root as the new root for the right part.
41        answer[1] = root;
42    }
43
44    // Return the pair of trees as the result of the split.
45    return answer;
46};
47

Time and Space Complexity

The given Python code defines a method splitBST that splits a Binary Search Tree (BST) into two trees. It partitions the BST such that all elements less than or equal to the target are in the left tree, and all elements greater than the target are in the right tree.

Time Complexity

The time complexity of the splitBST function is O(h), where h is the height of the BST. The algorithm works by performing a depth-first search (DFS) through the tree, splitting at each node based on the target. Since each node is visited at most once in a DFS traversal, and the depth of a DFS is proportional to the height of the tree, the overall time complexity is a function of the tree's height.

For a balanced tree, the height h would be log(n), where n is the number of nodes, resulting in a time complexity of O(log(n)). For an unbalanced tree, in the worst case, the height could be n, leading to a time complexity of O(n).

Space Complexity

The space complexity of the splitBST function is O(h). In practice, this is due to the space used by the call stack during the recursive DFS traversal of the tree. As with the time complexity, the worst-case space complexity is when the tree is unbalanced, leading to a depth of n, and therefore a space complexity of O(n).

For a balanced tree, since the height of the tree would be log(n), the space complexity would be O(log(n)).

So, the complexities depend on the balance of the BST:

For a balanced tree: Time Complexity: O(log(n)), Space Complexity: O(log(n))
For an unbalanced tree: Time Complexity: O(n), Space Complexity: O(n)

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don’t know