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.

*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]