How to dequeue and return the root of an binary search tree?

Question

So I've been working on this problem where I'm building a Binary Search Tree. Ive got every method to work, even have junit test done.

But the problem comes when i use the method dequeue()

public Node dequeue() {
    return root = delete(root, root.key);
}

which in turn uses the method delete(root, root.key)

Node delete(Node root, Integer key) {

    if (root == null)
        return root;

    if (key < root.key)
        root.left = delete(root.left, key);
    else if (key > root.key)
        root.right = delete(root.right, key);
    else {
        if (root.left == null)
            return root.right;
        else if (root.right == null)
            return root.left;
        
        root.key = succesor(root.right);
        root.right = delete(root.right, root.key);
    }

    return root;
}

int succesor(Node root) {
    int minv = root.key;

    while (root.left != null) {
        minv = root.left.key;
        root = root.left;
    }
    return minv;
}

What this code does is remove the root value and replace it with the smallest in the right subtree and then it should return the removed root value but instead i get the new root value.

Ex with a junit test:

    @Test
@DisplayName("Dequeue Test")
void test6() {
    que.enqueue(10);
    que.enqueue(5);
    que.enqueue(6);
    que.enqueue(15);
    que.enqueue(14);
    que.enqueue(13);

    assertEquals(10, que.dequeue().key);
    assertEquals(13, que.dequeue().key);
    assertEquals(14, que.dequeue().key);

}

Where you can see in the method que.enqueue(10); is now the root value. After inserting all of the values in the test we come to assertEquals(10, que.dequeue().key);, where i expect 10 but i get the new root which is 13.

Im aware that my root value changes when i call root.key = succesor(root.right); and i need something that could capture that 10 before the tree gets remade but im clueless to what.

So how can i capture 10 before it gets changed to 13 in this case?

Answer 1

Store the former root in a local variable, then update the root field by deleting the former root, then return the former root.

public Node dequeue() {
   final Node formerRoot = root;
   root = delete(root, root.key);
   return formerRoot;
}

Edit: There is an issue in your delete(...) method. It modifies the root object:

root.key = succesor(root.right);
root.right = delete(root.right, root.key);

This means that the Node object returned from dequeue() now contains the key of the new root instead of the dequeued one. To fix this, replace this two lines from delete(...) by something like:

final Node newRoot = new Node();
newRoot.key = succesor(root.right);
newRoot.left = root.left;
newRoot.right = delete(root.right, root.key);
return newRoot;

This will keep the original data in the dequeued root object and copy the data of the new root to a new Node object.