savchenko.tech / software engineering blog by Maryna Savchenko

Binary Search Tree: Part 2 min, floor, delete. Algorithms series

2022-07-14

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:

    @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:

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:

    @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:

    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.