Algorithmic problem solving & Java

/*
 * 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;
    }
}
/*
 * 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);
    }
}

Get updates?

As usual, if you find any of my posts useful support us by  buying or even trying one of our products and leave us a review on the app store.

[appbox appstore 1020072048]

[appbox appstore 1066820078]

[appbox appstore 1367294518]

[appbox appstore 1468791922]

[appbox googleplay com.mydaytodo.android.numbersgame]

[appbox appstore  1468826652]

[appbox appstore  1470834613]

[appbox googleplay com.mydaytodo.simplenotes]

[appbox appstore  1478331765]


0 Comments

Leave a Reply

Avatar placeholder

Your email address will not be published.

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
Best Wordpress Adblock Detecting Plugin | CHP Adblock