Split binary search tree
Given the BST tree, we have to split the tree based on input (N) into two subtrees, where subtree1 consists of all nodes that are less than or equal to N, and subtree 2 consists of all nodes that are greater than N.
50 / \ 40 60 / \ / 30 45 55 \ 58
output:
50 / 40 / \ 30 45 60 / 55 \ 58
I came up with the following algorithm, but it doesn't work correctly:
static Node splitTree(Node root, Node root2, int k){
if(root == null)
return null;
while(root != null){
if(root.data > k)
root = root.left;
else if(root.data < k)
root = root.right;
else
{
root2=root.right;
root.right=null;
break;
}
}
return root2;
}
source to share
You don't need an argument root2
, as this is the result of a function and any value will be passed anyway.
The splitting algorithm in the general case would have to not only cut an edge (creating two trees), but also repeat this at deeper levels of the clipping tree, since there may be subtrees that must be attached to the location where the clipping occurred.
For example, if your tree looks like this:
16
+---------------+---------------+
8 24
+-------+-------+ +-------+-------+
4 12 20 28
+---+---+ +---+---+ +---+---+ +---+---+
2 6 10 14 18 22 26 30
+-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31
And you want to carve with k = 11
, then the two trees will look like this:
8
+-------+-------+
4 10
+---+---+ +---+---+
2 6 9 11
+-+-+ +-+-+
1 3 5 7
16
+---------------+---------------+
12 24
+-------+ +-------+-------+
14 20 28
+---+---+ +---+---+ +---+---+
13 15 18 22 26 30
+-+-+ +-+-+ +-+-+ +-+-+
17 19 21 23 25 27 29 31
Note that there are several edges that have been cut and replaced: 16-8 is replaced with 16-12, and 8-12 is replaced with 8-10. This can be repeated multiple times and corresponds to the number of side switches (between left and right) that need to be done to find the target value (place for) in the tree.
Suggested Code:
static void setChild(Node node, boolean toLeft, Node child){
// Assign child node to the indicated direction: left or right
if (toLeft) {
node.left = child;
} else {
node.right = child;
}
}
static Node splitTree(Node root, int k){
Node root2 = null;
Node parent1 = null;
Node parent2 = null;
// Determine at which side of the root we will travel
boolean toLeft = root != null && k < root.data;
while (root != null) {
while (root != null && (k < root.data) == toLeft) {
parent1 = root;
root = toLeft ? root.left : root.right;
}
setChild(parent1, toLeft, null); // Cut out the edge. root is now detached
toLeft = !toLeft; // toggle direction
if (root2 == null) {
root2 = root; // This is the root of the other tree.
} else if (parent2 != null) {
setChild(parent2, toLeft, root); // re-attach the detached subtree
}
parent2 = parent1;
parent1 = null;
}
return root2;
}
See how it works on repl.it
source to share
public TreeNode[] splitBST(TreeNode root, int V) {
if (root == null) {
return new TreeNode[] { null, null };
}
if (root.val > V) {
TreeNode[] l = splitBST(root.left, V);
root.left = l[1];
return new TreeNode[] { l[0], root };
} else {
TreeNode[] r = splitBST(root.right, V);
root.right = r[0];
return new TreeNode[] { root, r[1] };
}
}
source to share
We can make the problem simple with recursion.
We create a function that returns a pair of nodes in the required split trees
class pair{
node small, big;
}
Our function looks like this: pair splitBST(node root, int k)
Algo:
1 //check if root is null, both trees are empty
if (root == null)
return pair(null, null)
2 //check if root.data > k. In this case we know that nodes smaller than k lies in left subtree since it given that we have BST
//Also, root will become part of pair.big
if (root.data > k)
pair leftAns = splitBST(root.left, k)
//this contains two trees-small and big where big needs to be updated as there might be nodes in left subtree that are greater than k
root.left = leftAns.big
leftAns.big = root
return leftAns
3 //for all other cases, we have to scan right subtree. This time root will become part of pair.small
pair rightAns = splitBST(root.right, k)
root.right = rightAns.small
rightAns.small = root
return rightAns
Note . In a thoughtful recursive solution, ALWAYS assume that my function returns the correct answer in all cases; don't think HOW it does it.
source to share