## Algorithmic problem solving & Java

``````/*
* Author: Bhuman Soni
*/

/*
* 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
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;
}
if(node.left != null) {
}
if(node.right != null) {
}
}
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
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);
}
}``````

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 appstore  1468826652]

[appbox appstore  1470834613]