Given a BST tree, we have to break the tree depending on the input(N), into two subtrees, where subtree1 consists of all the nodes, which are less than or equal to N and subtree2 consists of all the nodes which are greater than N.
50
/ \
40 60
/ \ /
30 45 55
\
58
output:
50
/
40
/ \
30 45
60
/
55
\
58
I have come up with following algorithm but its not working 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;
}
You would not need the root2 argument, since that is the result of the function, and whatever value would be passed would be overwritten anyway.
The algorithm to split would in general not only need to cut an edge (making two trees), but also repeat this at deeper levels of the cut-off tree, since there may be subtrees there that should be attached at the place the cut-off happened.
For instance, 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 cut with k = 11, then the two trees would 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 how there are several edges that were cut and replaced: 16-8 is replaced with 16-12, and 8-12 is replaced with 8-10. This can repeat several times, and corresponds to the number side-switches (between left and right) one has to make to find the (place for the) target value 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;
}