An important feature of Binary Search Tree (BST) is that it allows keeping keys in order. So we are able to apply wide range of operations that involves relative key order.

In this article we will take a look at some of them.

As in the previous part we will use TDD to ensure algorithm correctness.

MIN

min() method should return the smallest key.

    @Test
    void shouldReturnMinKeyInBST() {
        BinarySearchTree<Integer, String> bst = new BinarySearchTree<>();
        bst.put(23, "value1");
        bst.put(15, "value2");
        bst.put(56, "value3");
        bst.put(7, "value4");
        bst.put(71, "value5");

        assertEquals(7, bst.min());
    }

The implementation of MIN key is quite simple, we need to go left recursively until left node is null.

    public Key min() {
        return min(root).key;
    }

    private Node min(Node node) {
        if (node.left == null) return node;
        return min(node.left);
    }

The implementation of MAX key will be the same, only we need to go recursively right.

Floor and ceiling

floor() method should return the largest key less than or equal to given key.

ceiling() method should return smallest key grater than or equal to given key. bst_floor_ceiling.png

Test cases for floor() should check:

  • that floor of an existing key in BST returns same key
  • that floor returns the largest key that less than given key
    @Test
    void shouldReturnFloorWhenGivenKeyIsEqual() {
        BinarySearchTree<Integer, String> bst = new BinarySearchTree<>();
        bst.put(23, "value1");
        bst.put(14, "value2");
        bst.put(32, "value3");

        assertEquals(14, bst.floor(14));
    }

    @Test
    void shouldReturnFloorWhenGivenKeyIsLarger() {
            BinarySearchTree<Integer, String> bst = new BinarySearchTree<>();
        bst.put(23, "value1");
        bst.put(14, "value2");
        bst.put(32, "value3");
        bst.put(36, "value4");
        bst.put(33, "value5");

        assertEquals(33, bst.floor(34));
        }

In the implementation we compare given key to the key of a Node to find Subtree first, and then key that smaller or equals to the key.

    public Key floor(Key key) {
        Node node = floor(root, key);
        if (node == null) return null;
        return node.key;
    }

    private Node floor(Node node, Key key) {
        if (node == null) return null;
        int keyCmp = key.compareTo(node.key);
        if (keyCmp == 0) {
            return node;
        }
        if (keyCmp < 0) return floor(node.left, key);
        Node rightNode = floor(node.right, key);
        if (rightNode != null) return rightNode;
        else return node;
    }

ceiling() implementation will be the same as floor() with right, left and <, > interchanged.

DELETE

Deletion in the BST can seem tricky, when you do not stare at those trees few days in a row. First, we need to implement deleteMit() method. So it can be reused later in deletion.

Test case should check that there is no key present after deletion.

    @Test
    void shouldDeleteMinElement() {
        BinarySearchTree<Integer, String> bst = new BinarySearchTree<>();
        bst.put(23, "value1");
        bst.put(14, "value2");
        bst.put(32, "value3");

        bst.deleteMin();

        assertNull(bst.get(14));
    }

To delete element with a minimal key we need to go through next steps:

  • find the minimal node - go left until left node is null
  • remove it - replace node to be deleted with the child right node
  • update node number

bst_delete_min.png

    public void deleteMin() {
        root = deleteMin(root);
    }

    private Node deleteMin(Node node) {
        if (node.left == null) {
            return node.right;
        }
        node.left = deleteMin(node.left);
        node.subtreeNodeNumber = size(node.left) + size(node.right) + 1;
        return node;
    }

With the deleteMin() in place we can proceed with delete.

Test cases for delete() should check:

  • that there is no key present
  • that successor of deleted element is correct
    @Test
    void shouldDeleteElementByGivenKey() {
        BinarySearchTree<Integer, String> bst = new BinarySearchTree<>();
        bst.put(23, "value1");
        bst.put(14, "value2");
        bst.put(32, "value3");
        bst.put(36, "value4");
        bst.put(33, "value5");

        bst.delete(32);

        assertNull(bst.get(32));
    }

    @Test
    void successorShouldBeTheMinKeyInRightSubtree() {
        BinarySearchTree<Integer, String> bst = new BinarySearchTree<>();
        bst.put(23, "value1");
        bst.put(14, "value2");
        bst.put(32, "value3");
        bst.put(36, "value4");
        bst.put(28, "value5");
        bst.put(33, "value6");
        bst.put(45, "value7");
        bst.put(61, "value8");
        bst.put(41, "value9");
        bst.put(50, "value10");

        bst.delete(36);

        assertEquals(41, bst.root.right.right.key);
    }

So, we need next steps to implement deletion:

  • find the node by comparing the key
  • if node to delete has only one child, we simply replace it with a child node
  • save the node to be deleted
  • get the successor, which is minimal value of the right subtree min(node.right)
  • apply deleteMin() because we need to replace successor’s node (left node) with the right node in this subtree
  • left link of the successor will be the left node to be deleted bst_delete.png
    public void delete(Key key) {
        root =delete(root, key);
    }

    private Node delete(Node node, Key key) {
        if (node == null) {
            return null;
        }
        int cmp = key.compareTo(node.key);
        if (cmp < 0) {
            node.left = delete(node.left, key);
        }
        if (cmp > 0) {
            node.right = delete(node.right, key);
        } else {
            if (node.right == null) return node.left;
            if (node.left == null) return node.right;
            Node nodeToDelete = node;
            // find successor
            node = min(nodeToDelete.right);
            node.left = nodeToDelete.left;
            node.right = deleteMin(nodeToDelete.right);

        }
        node.subtreeNodeNumber = size(node.left) + size(node.right) + 1;
        return node;
    }

Complete implementation with test cases can be found on GitHub.

Sources:

  1. Algorithms by Robert Sedgewick.
  2. Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.