Split a binary search Tree

Question

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;


}

Answer 1

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;
}

See it run on repl.it

Answer 2

We can do the problem simply with recursion.

We create a function that returns pair of nodes to 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's 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: While thinking recursive solution, ALWAYS assume that my function returns the correct answer in all cases; don't think HOW it does so.

Answer 3

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] };
  }
}