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;


}

Solution 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

Solution 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.

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

Comments

[amrender singh]

what if root.data < k && direction ==right, than inner while loop will not run for first time and parent1 will still be null , so parent1[direction] = null will throw an null pointer exception.

[trincot]

This should not happen: direction is initialised with a value so that the inner loop will run at least once, and that loop will only exit when k < root.data is no longer true. This means that if there is a next iteration of the outer loop, the inner loop is guaranteed to run again at least one time (the direction has toggled). Did you have a case of a null pointer exception there?

[amrender singh]

if N=31, than direction will be right and k > root.data for the very first case only,so parent1 will still be null.

[trincot]

Did you actually run it? If k > root.data and direction == 'right' then the inner while loop will not exit, so parent1 will be non-null. Note that the while condition will then be root != null && (false) == (false) which is true.

[trincot]

I updated the code a bit so the string direction is now a boolean toLeft. This should run without errors.

[trincot]

You're welcome ;-) Depending on what you want, you might need to replace k < root.data with k <= root.data, although the latter is less standard.

[amrender singh]

Please can you explain this solution a bit?

[littletiger]

@amrendersingh Because this recursive function will always return TreeNode[0] and TreeNode[1], TreeNode[0] will be the result that node value <= V and TreeNode[1] will contains all the node that value > V.