BinarySearchTree and Testing

BinarySearchTree.java

package bst;

import java.util.LinkedList;
import java.util.List;

public class BinarySearchTree {

    private Node root = null;

    public boolean find(int id) {
        Node current = root;

        while(current != null) {
            if(current.data == id) {
                return true;
            } else if (current.data > id) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return false;
    }

    public void insert(int id) {
        Node newNode = new Node(id);
        if(root == null) {
            root = newNode;
            return;
        }

        Node current = root;
        Node parent = null;
        while(true) {
            parent = current;
            if(id < current.data) {
                current = current.left;
                if(current == null) {
                    parent.left = newNode;
                    return;
                }
            } else {
                current = current.right;
                if(current == null) {
                    parent.right = newNode;
                    return;
                }
            }
        }
    }

    public void iterate(Node root, List<Integer> results) {
        if(root != null) {
            iterate(root.left, results);
            results.add(root.data);
            iterate(root.right, results);
        }
    }

    public List<Integer> getInOrder() {
        LinkedList<Integer> result = new LinkedList<>();
        iterate(this.root, result);
        return result;
    }

    public boolean delete(int id) {
        Node parent = root;
        Node current = root;

        boolean isLeftChild = false;
        while(current.data != id) {
            parent = current;

            if(current.data > id) {
                isLeftChild = true;
                current = current.left;
            } else {
                isLeftChild = false;
                current = current.right;
            }

            if(current == null) {
                return false;
            }
        }

        // if i'm here that means we have found the node
        // Case 1: if the node to be deleted has no children
        if(current.left == null && current.right == null) {
            if(current == root) {
                root = null;
            }
            if(isLeftChild) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        }
        // Case 2: if the node to be deleted has only one child
        else if(current.right == null) {
            if(current == root) {
                root = current.left;
            } else if(isLeftChild) {
                parent.left = current.left;
            } else {
                parent.right = current.left;
            }
        } else if (current.left == null) {
            if(current == root) {
                root = current.right;
            } else if(isLeftChild) {
                parent.left = current.right;
            } else {
                parent.right = current.right;
            }
        } else if (current.left != null && current.right != null) {

            // now we have found minimum element in the right sub tree
            Node successor = getSuccessor(current);

            if(current == root) {
                root = successor;
            } else if (isLeftChild) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }
            successor.left = current.left;
        }
        return true;
    }

    public Node getSuccessor(Node deleteNode) {
        while(deleteNode.right != null) {
            deleteNode = deleteNode.right;
        }
        return deleteNode;
    }

    class Node {
        int data;
        Node left;
        Node right;

        public Node(int data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }
}

BinarySearchTreeTest.java

package bst;

import org.hamcrest.CoreMatchers;
import org.junit.After;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

import java.io.ByteArrayOutputStream;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.List;

public class BinarySearchTreeTest {


    private final ByteArrayOutputStream outContent = new ByteArrayOutputStream();
    private final ByteArrayOutputStream errContent = new ByteArrayOutputStream();
    private final PrintStream originalOut = System.out;
    private final PrintStream originalErr = System.err;

    @Before
    public void setUpStreams() {
        System.setOut(new PrintStream(outContent));
        System.setErr(new PrintStream(outContent));
    }

    @After
    public void restoraStreams() {
        System.setOut(new PrintStream(originalOut));
        System.setErr(new PrintStream(originalErr));
    }

    @Test
    public void testBST() {
        //give
        BinarySearchTree tree = new BinarySearchTree();

        //when
        tree.insert(3);
        tree.insert(8);
        tree.insert(1);
        tree.insert(4);
        tree.insert(6);
        tree.insert(2);
        tree.insert(10);
        tree.insert(9);
        tree.insert(20);
        tree.insert(25);
        tree.insert(15);
        tree.insert(16);

        //then

        List<Integer> results = tree.getInOrder();
        Assert.assertThat(results, CoreMatchers.equalTo(Arrays.asList(1,2,3,4,6,8,9,10,15,16,20,25)));
        Assert.assertThat(tree.find(4), CoreMatchers.is(true));
    }

    @Test
    public void testBSTDeletionSimple() {
        //given
        BinarySearchTree tree = new BinarySearchTree();

        //when
        tree.insert(3);
        tree.insert(8);
        tree.insert(1);

        //then
        tree.delete(8);
        List<Integer> results = tree.getInOrder();

        Assert.assertThat(results, CoreMatchers.equalTo(Arrays.asList(1,3)));
    }

    @Test
    public void testBST_removingComplex() {
        //give
        BinarySearchTree tree = new BinarySearchTree();

        //when
        tree.insert(3);
        tree.insert(8);
        tree.insert(1);
        tree.insert(4);
        tree.insert(6);
        tree.insert(2);
        tree.insert(10);
        tree.insert(9);
        tree.insert(20);
        tree.insert(25);
        tree.insert(15);
        tree.insert(16);
        tree.delete(10);

        //then

        List<Integer> results = tree.getInOrder();
        Assert.assertThat(results, CoreMatchers.equalTo(Arrays.asList(1,2,3,4,6,8,9,15,16,20,25)));
        Assert.assertThat(tree.find(4), CoreMatchers.is(true));
        Assert.assertThat(tree.find(100), CoreMatchers.is(false));
    }

    @Test
    public void testAllScope() {
        //given
        BSTDelete3 tree = new BSTDelete3();

        //when
        tree.insertKey(3);
        tree.insertKey(8);
        tree.insertKey(1);
        tree.insertKey(4);
        tree.insertKey(6);
        tree.insertKey(2);
        tree.insertKey(10);
        tree.insertKey(9);
        tree.insertKey(20);
        tree.insertKey(25);
        tree.insertKey(15);
        tree.insertKey(16);


        //then
        tree.inorder();

        Assert.assertEquals("1\n2\n3\n4\n6\n8\n9\n10\n15\n16\n20\n25\n",
                outContent.toString());
        outContent.reset();

        // delete
        tree.deleteKey(6);
        tree.inorder();

        Assert.assertEquals("1\n2\n3\n4\n8\n9\n10\n15\n16\n20\n25\n",
                outContent.toString());


        // search ( no exception thrown means result exist
        tree.search(tree.root, 8);
    }
}