How to make an efficient algorithm for chopping a binary search tree into two by given value?

Question

I implemented public BinarySearchTree<Node,T> chop(T x) that chops my tree into two parts at element x. The SSet this will contain elements < x, and the returned SSet is a SSet that contains elements >= x. This should work for all elements regardless of whether they are in this.

For example, suppose s={2,4,6,8}. Then s.chop(3) returns {4,6,8} and s becomes {2}. We would get the same result for s.chop(4).

The slowChop method is implemented, but it has a time complexity of O(n), but I need to reduce it to at least O(h) when the tree is balanced (where h is the height of the tree).

public BinarySearchTree<Node,T> slowChop(T x) {
    Node sample = super.newNode();
    BinarySearchTree<Node,T> other = new 
    BinarySearchTree<Node, T>(sample);

    // Iterate through the n nodes in-order.
    // When see value >=x, add to new BST in O(height) time, and
    // remove it from this BST (on next iteration) in O(height) time.
        Iterator<T> it = iterator();
    T prev = null;
    while( it.hasNext() ) {
      T curr = (T)(it.next());
      if( c.compare(curr, x) >= 0 ) { // we have our first >= x 
other.add(curr);
        if( prev != null ) {
          this.remove(prev);          // safe to remove now
        }
        prev = curr;
      }
    }
    if( prev != null ) {
      this.remove(prev); // edge case, get that last one!
    }
    return other; 
}

 public BinarySearchTree<Node,T> chop(T x) {
        Node sample = super.newNode();
        BinarySearchTree<Node,T> other = new 
        BinarySearchTree<Node, T>(sample);
    // TODO: Implement this method. It should match slowChop in
    // behaviour, but should be faster :-)
    

    
    return other;
  }

Answer 1

Indeed, your algorithm is not making use of the efficiency that you can get from the fact you are dealing with a binary search tree. So iterating through the tree with an in-order traversal is not the way to go.

Instead, perform a binary search and cut the edges that link two nodes which should end up in different trees. While cutting you'll also need to reattach nodes to where a previous cut was performed. The complexity is the same as a binary search towards the bottom of the tree, and so it is O(logn).

Here is an implementation that assumes you have the regular getters and setters:

• on the Node class: getLeft, setLeft, getRight, setRight, getValue, and
• on the BinarySearchTree class: getRoot, setRoot

public BinarySearchTree<Node,T> chop(T x) {
    // Create two temporary dummy (sentinel) nodes to ease the process.
    Node rightRootParent = super.newNode();
    Node leftRootParent = super.newNode();
    
    // Set "cursors" at both sides
    Node rightParent = rightRootParent;
    Node leftParent = leftRootParent;
    
    // Start the binary search for x, cutting edges as we walk down
    Node node = this.getRoot();
    while (node != null) {
        // Decide for each node in the binary search path at which side it should go
        if (c.compare(node.getValue(), x) >= 0) {
            // Node should belong to the right-side tree
            rightParent.setLeft(node); // Establish edge
            rightParent = node; 
            node = node.getLeft(); // Move down
            rightParent.setLeft(null); // Cut next edge for now (it might get restored)
        } else { // Symmetric case
            leftParent.setRight(node);
            leftParent = node;
            node = node.getRight();
            leftParent.setRight(null);
        }
    }
    
    // Set the roots of both trees
    this.setRoot(leftRootParent.getRight());
    return BinarySearchTree<Node, T>(rightRootParent.getLeft());
}