776. Split BST
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.
Which one best describes the time complexity of the following code?
1int factorial(int n) {
2 if (n < 0) {
3 return -1;
4 } else if (n == 0) {
5 return 1;
6 } else {
7 return n * factorial(n - 1);
8 }
9}
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
dfsfunction encounters aNonenode (the base case), it returns a pair ofNonenodes, indicating the end of a branch. This is represented byreturn [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 calldfs(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 tol(the part of the right subtree that's less than or equal to the target). It then returns[root, r], whererootis now the root of the subtree with data less than or equal to the target andris 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 withdfs(root.left). It receives a pair of roots,lfor the left split (all nodes less than or equal to the target) andrfor the right split (all nodes greater than the target up to now). In this case,root.leftshould be updated tor(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 inl, and those that are greater than the target are underroot.
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.
Depth first search can be used to find whether two components in a graph are connected.
Example Walkthrough
Consider the following Binary Search Tree and the target value 3:
1 4 2 / \ 3 2 6 4 / \ / \ 5 1 3 5 7
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:
1 2 2 / \ 3 1 3The 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:
1Subtree less than or equal to 3: 2 2 3 / \ 4 1 3 5 6Subtree greater than 3: 7 4 8 \ 9 6 10 / \ 11 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)
371class 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}
501/**
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};
591// 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};
47What's the output of running the following function using input 56?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
271private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
301const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30Time 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.
Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
Binary Search Tree Intro Definition A Binary Search Tree or BST is a rooted binary tree with the value of each internal node being greater than all the values in the respective node's left subtree and less than the ones in its right subtree An empty tree is a BST since it satisfies the
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.