Binary Search Tree in Java with JUnit

I have been brushing up on my algorithmic coding skills and mate, are trees challenging or what? Yes they are a logical but difficult data structure to work with.

Algorithmic problem solving & Java

The most interesting thing about all this is, despite heavily coding in iOS Swift and Javascript usage over the last 4.5 years, I am still super comfortable with Java. I mean, I just know the API. I don’t even have to actively think about certain things. E.g. the other day I was like what’s a thread-safe synchronised data structure? It’s not ArrayList, but it’s Vector! Hence, naturally I decide to practice my algorithmic problem solving in Java.

Coding Swift does help with Java though. I mean, I saw the Predicates in Java 8. OMG!!!! I have done that in Swift and of course in Java 8, it has a very Java way of doing it haha. Actually it’s almost funny how super verbose it is compared to Swift, but ahh well, that’s Java for you. My first love!!!

Maybe because I have been using it since 2006 and from Java 1.3 🙂 Anyway, I was just getting my hands dirty with some random coding of Binary Search Trees (BST). I just wrote a few methods to create a BST from an array, search it using both Breadth First Search, recursive search and lastly, find the least common ancestors for two nodes. This time instead of just lazily testing code in the main class, I have written sophisticated JUnit tests for it.

/*
 * Author: Bhuman Soni
 */
import java.util.LinkedList;

/*
 * A standard Binary Search Tree Node which has both a left 
 * and a right node;
 */
class BSTNode {
    int data;
    //not declaring these variables as private to make
    //the code a little less verbose here
    BSTNode left;
    BSTNode right;

    public BSTNode(int data) {
        this.data = data;
        this.right = null;
        this.left = null;
    }
    public String toString() {
        return "" +data;
    }
}

public class TreePractice {

    /*
     * In this method we want to find whether or a node with a 
     * particular value exists in the tree or not.
     *  
     * Algorithm:
     * We traverse through the nodes of a tree and store the nodes 
     * we find in a queue.
     */
    public BSTNode valueExistsIn(BSTNode root, int data) {
        if(root == null) return null;

        //let's loop through this using a LinkedList
        LinkedList<BSTNode> queue = new LinkedList<BSTNode>();
        queue.add(root); //this would be the root node
        while(!queue.isEmpty()) {
            //we iterate through it
            BSTNode node = queue.removeFirst();
            if(node.data == data) {
                return node;
            }
            //let's not add null nodes
            if(node.left != null) {
                queue.add(node.left);
            }
            if(node.right != null) {
                queue.add(node.right);
            }
        }
        return null;
    }
    /*
     * the same solution as the one above, except we will do
     * it recursively
     */
    public BSTNode valueExistsInR(BSTNode root, int data) {
        //recursive function so the first thing is to add a termination condition
        if(root == null) return null;
        //let's check here, so this is like pre-order traversal
        if(root.data == data) {
            return root;
        }
        BSTNode existsInLeft = valueExistsInR(root.left, data);
        if(existsInLeft != null) { //that's it, break the recursive chain
            return existsInLeft;
        }
        return valueExistsInR(root.right, data);
    }
    /*
     * Let's re-write the algorithm to create a Binary Search Tree 
     * from an array of Integers.
     * Let's say we have an array of 1, 2, 3, 4, 5, 6 and divide 
     * length by 2 and we get 2 
     */
    public BSTNode createBst(int [] array, int start, int end) {
        if(array == null) return null;
        //we need another condition to avoid stack overflow
        //we only come in here, if start is < end
        if(start > end || start < 0 ) return null;
        //we do this and get our definitive mid point in the array
        int mid = (start + end) / 2;
        //create the root node
        BSTNode node = new BSTNode(array[mid]);
        //at this point, we have already taken a node for mid
        //so why bother creating it
        node.left = createBst(array, start, mid -1);
        node.right = createBst(array, mid+1, end);
        return node; // at this point, we would have recursed the hell out and have a BST
    }

    /*
     * Last method, find if 2 nodes of a given tree have
     * any common ancestors
     * Assumption, both target1 and target2 exist in the tree
     */
    public BSTNode hasCommonAncestor(BSTNode root, int target1, int target2) {
        //this is the base case because eventually we will hit a null node
        if(root == null) return null; //mandatory null check

        if(root.data > target1 && root.data > target2) {
            //this means, it's in the left sub-tree
            return hasCommonAncestor(root.left, target1, target2);
        }

        if(root.data < target1 && root.data < target2) {
            //the root data is greater that means, it's in the 
            //right sub-tree
            return hasCommonAncestor(root.right, target1, target2);
        }
        return root;
    }
}

Here’s the test harness for it.

/*
 * Author: Bhuman Soni
 */

import org.junit.Assert;
import org.junit.jupiter.api.AfterEach;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

class TreePracticeTest {

    BSTNode n1 = new BSTNode(1);
    BSTNode n2 = new BSTNode(2);
    BSTNode n3 = new BSTNode(3);
    BSTNode n4 = new BSTNode(4);
    BSTNode n5 = new BSTNode(5);
    BSTNode n6 = new BSTNode(6);

    TreePractice tp = new TreePractice();
    int [] arr = {1,2,3,4,5,6};
    BSTNode tree;

    /*  probably not the best because we will construct
        a tree before each test but anyway in this case
        our data is too small for us to worry about this. 
        Maybe if we had a massive test pool of creating
        some heavy JDBC connections and all, then maybe we
        can use something like the @BeforeClass method to
        prepare for the test only once. 
        JDBC: Ahh man, do they still call it that? am I 
        showing my age here? haha
    */

    @BeforeEach
    void setUp() throws Exception {
        tree = tp.createBst(arr, 0, arr.length - 1);
    }

    @AfterEach
    void tearDown() throws Exception {
    }

    @Test
    void testValueExistsIn() {
        BSTNode node = tp.valueExistsIn(tree, 4);

        Assert.assertTrue(node instanceof BSTNode);
        BSTNode nullNode = tp.valueExistsIn(tree, 99);
        Assert.assertNull(nullNode);
    }

    @Test
    void testValueExistsInR() {
        BSTNode node = tp.valueExistsInR(tree, 4);

        Assert.assertTrue(node instanceof BSTNode);

        BSTNode nullNode = tp.valueExistsIn(tree, 99);
        Assert.assertNull(nullNode);
    }
    @Test
    void testCreateBST() {
        /* we can just test whether or not we created
         * a proper BST because we create the tree in 
         * @BeforeEach method that runs before each test
         */
        Assert.assertEquals(3, tree.data);
    }
    @Test 
    void testCommonAncestor() {
        BSTNode node = tp.hasCommonAncestor(tree, 4, 6);
        Assert.assertTrue(node instanceof BSTNode);
        Assert.assertEquals(5, node.data);
    }
}

I hope you found this short post useful. Java is still fun to work with and they have definitely made improvements to the language to make it more modern. Although, I haven’t used any of those modern things here.

[appbox googleplay com.mydaytodo.simplenotes]