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

Like the blog? Subscribe for 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.

‎My Day To-Do - Smart Task List
‎My Day To-Do - Smart Task List
‎My Day To-Do Lite - Task list
‎My Day To-Do Lite - Task list
‎Snap! I was there
‎Snap! I was there
Developer: Bhuman Soni
Price: Free
Numbers Game: Calculation Master
Numbers Game: Calculation Master
‎Simple 'N' Easy: Todos & food
‎Simple 'N' Easy: Todos & food
‎Captain's Personal Log
‎Captain's Personal Log
Developer: Bhuman Soni
Price: $4.99
My Simple Notes
My Simple Notes
Developer: Bhuman Soni
Price: Free
‎My Simple Notes - Dictate
‎My Simple Notes - Dictate
Developer: Bhuman Soni
Price: $2.99

0 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *