I was looking at several articles on binary trees and thought it would be a good opportunity to write some Java code in order to refresh knowledge of binary trees, in particular with BSTs (Binary Search Trees). You never know what new things are out there.
I am not sure if most system architects and software developers run into the same situation as I do. I have learned and worked with many data structures and programming languages. I do not work with every single data structure often enough that I recall how to implement or use it as far as all the associated methods and functions. I have a reasonable understanding of most data structures and I can get back on the horse rather quickly.
The same holds when working with programming languages. Currently I am working in C/C++. Java and Python will be in the back burner for a few months. I recall (many years ago) a data structures class I took while attending Cornell University. The course which lasted a quarter, dealt primarily with stacks and queues. I recall the final project which was a simulation of a grocery store.
A few years after, I implemented from scratch an extensive library supporting multiple data structures. That library has grown with time. The library supports among others queue, stacks, list, hash tables, trees, etc. The queue implementation supports single and double link queues. It also implements priority queues. All that code has been implemented in C/C++. The code is / has been used in production for several products. That said, on occasions, if I need to work on an enhancement, it takes me a couple hours to get back on track.
One approach that I always use is TDD (Test Driven Development). As a 
matter of fact, I am writing a set of APIs for a storage server with very little overhead. The API is a limited set from an existing product. We have chosen a reduced set of calls to implement. They all use TCP/IP sockets for performance. When done I will do a port to Java which I will describe in this blog.
Enough background, and lets compute the distance between nodes in a BST. To get back on the horse we will implement and populate a BST. Will make sure things are working as we go. Once that is done, we will implement some tree traversal functions to verify that the BST is being built properly. At that point we can implement the function that computes the distance between two random nodes. I will try to describe my approach as we go through the process.
I will start with a blank project in Java using the Eclipse IDE. I will try to separate the classes in order to make them available for further experimentation. Will try using a test driven approach and hopefully I will be able to describe it with enough detail.
Following is the initial code for the project:
package bst.canessa;
import java.util.ArrayList;
/*
*
*/
public class Solution {
/*
* Build a BST and find the distance between nodes.
*/
public static void main(String[] args) {
// **** generate an array of unique integers in specified range ****
// **** use the array to create a BST ****
// **** loop finding the distance between nodes ****
// **** generate two values to determine the distance ****
// **** get the distance in the tree ****
}
}
We will generate a set of values for the nodes and place them into an array. To make it simpler to follow the numbers will be in a specified range. Once the pseudo random array of integers is created we can populate a BST with them.
I initially decided to loop of a pair of values but during the implementation dropped the idea. The program can just be run each time with a set of values. To do so, we need to generate a couple values which in some cases should be out of the specified range. This will be done to test the behavior of the class. Then we could generate the distance between the two nodes. The distance between two nodes in a BST is the number of edges that needs to be traversed from one node to the other.
Let’s generate a set of consecutive integers in a specified range and then shuffle them in a pseudo random order. This may be accomplished with the following code:
package bst.canessa;
import java.security.SecureRandom;
import java.util.HashSet;
import java.util.Random;
/*
*
*/
public class Solution {
/*
* Generate an array of random numbers in the specified range.
*/
static int[] arrayWithUniqueValues(int from, int to) throws Exception {
System.out.println("arrayWithUniqueValues <<< from: " + from + " to: " + to);
// **** determine the number of integers to generate ****
int n = to - from + 1;
System.out.println("arrayWithUniqueValues <<< n: " + n);
// **** declare and populate an array with the numbers in ascending order ****
int arr[] = new int[n];
for (int i = 0; i < n; i++)
arr[i] = from + i;
// **** declare and populate the random array ****
int[] rarr = new int[n];
int x = n;
SecureRandom srand = new SecureRandom();
for (int i = 0; i < n; i++) {
int k = srand.nextInt(x);
rarr[i] = arr[k];
arr[k] = arr[x - 1];
x--;
}
// **** check if we have a duplicate random number ****
HashSet<Integer> set = new HashSet<Integer>();
for (int i = 0; i < rarr.length; i++)
if (!set.add(rarr[i]))
throw new Exception("arrayWithUniqueValues <<< duplicate: " + rarr[i]);
if (set.size() != n)
throw new Exception("arrayWithUniqueValues <<< set.size() != n: " + n);
// **** display the random array ****
System.out.print("arrayWithUniqueValues <<< rarr: [");
for (int i = 0; i < rarr.length; i++) {
System.out.print(rarr[i]);
if (i < rarr.length - 1)
System.out.print(", ");
}
System.out.println("]");
// **** return the random array ****
return rarr;
}
/*
* Build a BST and find the distance between nodes.
*/
public static void main(String[] args) throws Exception {
// **** generate a range within the specified value ****
final int MAX_VAL = 32;
Random rand = new Random();
int[] range = {rand.nextInt(MAX_VAL), rand.nextInt(MAX_VAL)};
System.out.println("main <<< range: [" + range[0] + ", " + range[1] + "]");
// **** generate an array of unique random integers in the specified range ****
int[] values = arrayWithUniqueValues(Math.min(range[0], range[1]),
Math.max(range[0], range[1]));
// **** use the array to create a BST ****
// **** loop finding the distance between nodes ****
// **** generate two values to determine the distance ****
// **** get the distance in the tree ****
}
}
The console output follows:
main <<< range: [7, 22] arrayWithUniqueValues <<< from: 7 to: 22 arrayWithUniqueValues <<< n: 16 arrayWithUniqueValues <<< rarr: [22, 9, 17, 15, 21, 14, 12, 13, 16, 8, 18, 7, 19, 10, 20, 11]
We now need to insert the values into a BST. We could write code to build the array with a specific order, or just run code to insert the nodes as needed disregarding balancing the tree. This could be done with the following code:
package bst.canessa;
import java.security.SecureRandom;
import java.util.HashSet;
import java.util.Random;
/*
*
*/
public class Solution {
/*
* Generate an array of random numbers in the specified range.
*/
static int[] arrayWithUniqueValues(int from, int to) throws Exception {
System.out.println("arrayWithUniqueValues <<< from: " + from + " to: " + to);
// **** determine the number of integers to generate ****
int n = to - from + 1;
System.out.println("arrayWithUniqueValues <<< n: " + n);
// **** declare and populate an array with the numbers in ascending order ****
int arr[] = new int[n];
for (int i = 0; i < n; i++)
arr[i] = from + i;
// **** declare and populate the random array ****
int[] rarr = new int[n];
int x = n;
SecureRandom srand = new SecureRandom();
for (int i = 0; i < n; i++) {
int k = srand.nextInt(x);
rarr[i] = arr[k];
arr[k] = arr[x - 1];
x--;
}
// **** check if we have a duplicate random number ****
HashSet<Integer> set = new HashSet<Integer>();
for (int i = 0; i < rarr.length; i++)
if (!set.add(rarr[i]))
throw new Exception("arrayWithUniqueValues <<< duplicate: " + rarr[i]);
if (set.size() != n)
throw new Exception("arrayWithUniqueValues <<< set.size() != n: " + n);
// **** display the random array ****
System.out.print("arrayWithUniqueValues <<< rarr: [");
for (int i = 0; i < rarr.length; i++) {
System.out.print(rarr[i]);
if (i < rarr.length - 1)
System.out.print(", ");
}
System.out.println("]");
// **** return the random array ****
return rarr;
}
/*
* Build a BST and find the distance between nodes.
*/
public static void main(String[] args) throws Exception {
// **** generate a range within the specified value ****
final int MAX_VAL = 32;
Random rand = new Random();
int[] range = {rand.nextInt(MAX_VAL), rand.nextInt(MAX_VAL)};
System.out.println("main <<< range: [" + range[0] + ", " + range[1] + "]");
// **** generate an array of unique random integers in the specified range ****
int[] values = arrayWithUniqueValues(Math.min(range[0], range[1]),
Math.max(range[0], range[1]));
// **** use the random array to create a BST ****
BinaryTree tree = new BinaryTree();
for (int val : values) {
tree.insert(val);
}
// **** display the BST (inorder) ****
System.out.print("arrayWithUniqueValues <<< inorder: ");
tree.inorder(tree.getRoot());
// **** loop finding the distance between nodes ****
// **** generate two values to determine the distance ****
// **** get the distance in the tree ****
}
}
We will also create the BinaryTree class to represent our BST as follows:
package bst.canessa;
/*
*
*/
public class BinaryTree {
Node root;
// **** constructor ****
public BinaryTree() {
this.root = null;
}
// **** ****
public Node getRoot() {
return this.root;
}
// **** insert node ****
public void insert(int val) {
if (this.root == null)
this.root = new Node(val);
else insert(this.root, val);
}
// **** insert node ****
private void insert(Node node, int val) {
// **** insert to the left ****
if (val < node.getVal()) {
if (node.getLeftChild() == null) {
node.setLeftChild(new Node(val));
} else {
insert(node.getLeftChild(), val);
}
}
// **** insert to the right ****
else {
if (node.getRightChild() == null) {
node.setRightChild(new Node(val));
} else {
insert(node.getRightChild(), val);
}
}
}
// **** in order traversal ****
void inorder(Node node) {
if (node == null)
return;
inorder(node.getLeftChild());
System.out.print(node.getVal() + " ");
inorder(node.getRightChild());
}
}
In the previous code we make use of the Node class. The code for the Node class follows:
package bst.canessa;
/*
* Binary tree node
*/
public class Node {
// **** members ****
int data;
Node left;
Node right;
// **** constructor ****
public Node(int d) {
data = d;
left = right = null;
}
// **** ****
public int getVal() {
return this.data;
}
// **** ****
public Node getLeftChild() {
return this.left;
}
// **** ****
public void setLeftChild(Node left) {
this.left = left;
}
// **** ****
public Node getRightChild() {
return this.right;
}
// **** ****
public void setRightChild(Node right) {
this.right = right;
}
}
Once all this is done we could run a test and capture the console output:
main <<< range: [19, 28] arrayWithUniqueValues <<< from: 19 to: 28 arrayWithUniqueValues <<< n: 10 arrayWithUniqueValues <<< rarr: [25, 20, 27, 22, 19, 21, 23, 24, 28, 26] arrayWithUniqueValues <<< inorder: 19 20 21 22 23 24 25 26 27 28
Note that for a test we also included an in order tree traversal. This was done to verify that the insertion resulted in a proper BST. We should write the output of the in order traversal method to an array and then check the order and count or we could check the node values and counts as we traverse the BST. I am going to skip such checks and perform the verification just by eyeballing the number sequence. In actual projects we should always implement and run unit tests to verify expected results.
Let’s start the implementation of the distance between two randomly selected nodes in the BST by computing the distance from the root to a node. The code for such task follows:
package bst.canessa;
import java.security.SecureRandom;
import java.util.HashSet;
import java.util.Random;
/*
*
*/
public class Solution {
/*
* Generate an array of random numbers in the specified range.
*/
static int[] arrayWithUniqueValues(int from, int to) throws Exception {
System.out.println("arrayWithUniqueValues <<< from: " + from + " to: " + to);
// **** determine the number of integers to generate ****
int n = to - from + 1;
System.out.println("arrayWithUniqueValues <<< n: " + n);
// **** declare and populate an array with the numbers in ascending order ****
int arr[] = new int[n];
for (int i = 0; i < n; i++)
arr[i] = from + i;
// **** declare and populate the random array ****
int[] rarr = new int[n];
int x = n;
SecureRandom srand = new SecureRandom();
for (int i = 0; i < n; i++) {
int k = srand.nextInt(x);
rarr[i] = arr[k];
arr[k] = arr[x - 1];
x--;
}
// **** check if we have a duplicate random number ****
HashSet<Integer> set = new HashSet<Integer>();
for (int i = 0; i < rarr.length; i++)
if (!set.add(rarr[i]))
throw new Exception("arrayWithUniqueValues <<< duplicate: " + rarr[i]);
if (set.size() != n)
throw new Exception("arrayWithUniqueValues <<< set.size() != n: " + n);
// **** display the random array ****
System.out.print("arrayWithUniqueValues <<< rarr: [");
for (int i = 0; i < rarr.length; i++) {
System.out.print(rarr[i]);
if (i < rarr.length - 1)
System.out.print(", ");
}
System.out.println("]");
// **** return the random array ****
return rarr;
}
/*
* Build a BST and find the distance between nodes.
*/
public static void main(String[] args) throws Exception {
// **** generate a range within the specified value ****
final int MAX_VAL = 32;
Random rand = new Random();
int[] range = {rand.nextInt(MAX_VAL), rand.nextInt(MAX_VAL)};
System.out.println("main <<< range: [" + range[0] + ", " + range[1] + "]");
// **** generate an array of unique random integers in the specified range ****
int[] values = arrayWithUniqueValues(Math.min(range[0], range[1]),
Math.max(range[0], range[1]));
// **** use the random array to create a BST ****
BinaryTree tree = new BinaryTree();
for (int val : values) {
tree.insert(val);
}
// **** display the BST (inorder) ****
System.out.print("arrayWithUniqueValues <<< inorder: ");
tree.inorder(tree.getRoot());
System.out.println();
// **** loop finding the distance between nodes ****
// **** generate two values to determine the distance ****
int val1 = Math.min(range[0], range[1]) + 1;
int val2 = Math.max(range[0], range[1]) - 1;
System.out.println("main <<< val1: " + val1 + " val2: " + val2);
// **** find distance from root to val1 ****
// **** find distance from root to val2 ****
// **** find distance from root to LCA (Lowest Common Ancestor) ****
}
}
After the actual implementation of the method we would have the following code in the solution:
package bst.canessa;
import java.security.SecureRandom;
import java.util.HashSet;
import java.util.Random;
/*
*
*/
public class Solution {
/*
* Generate an array of random numbers in the specified range.
*/
static int[] arrayWithUniqueValues(int from, int to) throws Exception {
System.out.println("arrayWithUniqueValues <<< from: " + from + " to: " + to);
// **** determine the number of integers to generate ****
int n = to - from + 1;
System.out.println("arrayWithUniqueValues <<< n: " + n);
// **** declare and populate an array with the numbers in ascending order ****
int arr[] = new int[n];
for (int i = 0; i < n; i++)
arr[i] = from + i;
// **** declare and populate the random array ****
int[] rarr = new int[n];
int x = n;
SecureRandom srand = new SecureRandom();
for (int i = 0; i < n; i++) {
int k = srand.nextInt(x);
rarr[i] = arr[k];
arr[k] = arr[x - 1];
x--;
}
// **** check if we have a duplicate random number ****
HashSet<Integer> set = new HashSet<Integer>();
for (int i = 0; i < rarr.length; i++)
if (!set.add(rarr[i]))
throw new Exception("arrayWithUniqueValues <<< duplicate: " + rarr[i]);
if (set.size() != n)
throw new Exception("arrayWithUniqueValues <<< set.size() != n: " + n);
// **** display the random array ****
System.out.print("arrayWithUniqueValues <<< rarr: [");
for (int i = 0; i < rarr.length; i++) {
System.out.print(rarr[i]);
if (i < rarr.length - 1)
System.out.print(", ");
}
System.out.println("]");
// **** return the random array ****
return rarr;
}
/*
* Build a BST and find the distance between nodes.
*/
public static void main(String[] args) throws Exception {
// **** generate a range within the specified value ****
final int MAX_VAL = 16;
Random rand = new Random();
int[] range = {rand.nextInt(MAX_VAL) + 1, rand.nextInt(MAX_VAL) + 1};
System.out.println("main <<< range: [" + range[0] + ", " + range[1] + "]");
// **** generate an array of unique random integers in the specified range ****
int[] values = arrayWithUniqueValues(Math.min(range[0], range[1]),
Math.max(range[0], range[1]));
// **** use the random array to create a BST ****
BinaryTree tree = new BinaryTree();
for (int val : values) {
tree.insert(val);
}
// **** display the value of the root node****
System.out.println("main <<< root.val: " + tree.getRoot().getVal());
// **** display the BST (inorder) ****
System.out.print("arrayWithUniqueValues <<< inorder: ");
tree.inorder(tree.getRoot());
System.out.println();
// **** generate two values to determine the distance ****
int val1 = Math.min(range[0], range[1]) + rand.nextInt(MAX_VAL / 3);
int val2 = Math.max(range[0], range[1]) - rand.nextInt(MAX_VAL / 3);
System.out.println("main <<< val1: " + val1 + " val2: " + val2);
// **** find distance from root to val1 ****
int dist1 = tree.distRootToVal(tree.getRoot(), val1);
System.out.println("main <<< dist1: " + dist1);
// **** find distance from root to val2 ****
int dist2 = tree.distRootToVal(tree.getRoot(), val2);
System.out.println("main <<< dist2: " + dist2);
// **** find distance from root to LCA (Lowest Common Ancestor) ****
}
}
The corresponding method in the BinaryTree class follows:
// **** find distance from root to the node with the specified value ****
public int distRootToVal(Node root, int val) {
// **** base case (to end recursion) ****
if (root == null)
return -1;
// **** initialize the distance ****
int dist = -1;
// **** check if value is in this node or in one of it's children ****
if ((root.getVal() == val) ||
(dist = distRootToVal(root.getLeftChild(), val)) >= 0 ||
(dist = distRootToVal(root.getRightChild(), val)) >= 0)
return dist + 1;
// **** ****
return dist;
}
Let’s see a sample output captured from the console:
main <<< range: [2, 7] arrayWithUniqueValues <<< from: 2 to: 7 arrayWithUniqueValues <<< n: 6 arrayWithUniqueValues <<< rarr: [4, 5, 3, 6, 7, 2] main <<< root.val: 4 arrayWithUniqueValues <<< inorder: 2 3 4 5 6 7 main <<< val1: 6 val2: 3 main <<< dist1: 2 main <<< dist2: 1
In order to determine the distance between two nodes, we need to find the lowest common ancestor. Let’s take a look at a diagram:
10(root)
/\
8 11
/ \ \
7 9 15
distance(7, 9) = 2
We can compute the distance from the root to node 7. We can then compute the distance from the root to node 9. We could then determine the distance between nodes 7 and 9. Let’s look at the code in our solution:
package bst.canessa;
import java.security.SecureRandom;
import java.util.HashSet;
import java.util.Random;
/*
*
*/
public class Solution {
/*
* Generate an array of random numbers in the specified range.
*/
static int[] arrayWithUniqueValues(int from, int to) throws Exception {
System.out.println("arrayWithUniqueValues <<< from: " + from + " to: " + to);
// **** determine the number of integers to generate ****
int n = to - from + 1;
System.out.println("arrayWithUniqueValues <<< n: " + n);
// **** declare and populate an array with the numbers in ascending order ****
int arr[] = new int[n];
for (int i = 0; i < n; i++)
arr[i] = from + i;
// **** declare and populate the random array ****
int[] rarr = new int[n];
int x = n;
SecureRandom srand = new SecureRandom();
for (int i = 0; i < n; i++) {
int k = srand.nextInt(x);
rarr[i] = arr[k];
arr[k] = arr[x - 1];
x--;
}
// **** check if we have a duplicate random number ****
HashSet<Integer> set = new HashSet<Integer>();
for (int i = 0; i < rarr.length; i++)
if (!set.add(rarr[i]))
throw new Exception("arrayWithUniqueValues <<< duplicate: " + rarr[i]);
if (set.size() != n)
throw new Exception("arrayWithUniqueValues <<< set.size() != n: " + n);
// **** display the random array ****
System.out.print("arrayWithUniqueValues <<< rarr: [");
for (int i = 0; i < rarr.length; i++) {
System.out.print(rarr[i]);
if (i < rarr.length - 1)
System.out.print(", ");
}
System.out.println("]");
// **** return the random array ****
return rarr;
}
/*
* Build a BST and find the distance between nodes.
*/
public static void main(String[] args) throws Exception {
// **** generate a range within the specified value ****
final int MAX_VAL = 16;
Random rand = new Random();
int[] range = {rand.nextInt(MAX_VAL) + 1, rand.nextInt(MAX_VAL) + 1};
System.out.println("main <<< range: [" + range[0] + ", " + range[1] + "]");
// **** generate an array of unique random integers in the specified range ****
int[] values = arrayWithUniqueValues(Math.min(range[0], range[1]),
Math.max(range[0], range[1]));
// **** use the random array to create a BST ****
BinaryTree tree = new BinaryTree();
for (int val : values) {
tree.insert(val);
}
// **** display the value of the root node****
System.out.println("main <<< root.val: " + tree.getRoot().getVal());
// **** display the BST (inorder) ****
System.out.print("arrayWithUniqueValues <<< inorder: ");
tree.inorder(tree.getRoot());
System.out.println();
// **** generate two values to determine the distance ****
int val1 = Math.min(range[0], range[1]) + rand.nextInt(MAX_VAL / 3);
int val2 = Math.max(range[0], range[1]) - rand.nextInt(MAX_VAL / 3);
System.out.println("main <<< val1: " + val1 + " val2: " + val2);
// **** find distance from root to val1 ****
int dist1 = tree.distRootToVal(tree.getRoot(), val1);
System.out.println("main <<< dist1: " + dist1);
// **** find distance from root to val2 ****
int dist2 = tree.distRootToVal(tree.getRoot(), val2);
System.out.println("main <<< dist2: " + dist2); // **** find distance from root to LCA (Lowest Common Ancestor) **** if ((dist1 > 0) &&
(dist2 > 0)) {
Node lca = tree.lca(tree.getRoot(), val1, val2, 0);
if (lca != null)
System.out.println("main <<< lca = " + lca.toString());
else
System.out.println("main <<< lca == null");
}
// **** ****
}
}
The lca method used to finding the LCA in the BST follows:
// **** find lca (Lowest Common Ancestor) ****
public Node lca(Node root, int val1, int val2, int rootDist) {
// **** base case (to end recursion) ****
if (root == null)
return null;
// **** ****
if (root.getVal() == val1)
return root;
if (root.getVal() == val2)
return root;
// **** ****
Node leftLCA = lca(root.getLeftChild(), val1, val2, rootDist + 1);
Node rightLCA = lca(root.getRightChild(), val1, val2, rootDist + 1);
// **** ****
if ((leftLCA != null) &&
(rightLCA != null))
return root;
// **** ****
return (leftLCA != null) ? leftLCA : rightLCA;
}
I also added a method to display a Node. Thought of displaying mode information, but I ran out of time. The code follows:
// **** ****
public String toString() {
return "val: " + getVal();
}
To see how far we are let’s take a look at some output from the console:
main <<< range: [14, 4] arrayWithUniqueValues <<< from: 4 to: 14 arrayWithUniqueValues <<< n: 11 arrayWithUniqueValues <<< rarr: [9, 5, 12, 14, 4, 11, 10, 8, 6, 7, 13] main <<< root.val: 9 arrayWithUniqueValues <<< inorder: 4 5 6 7 8 9 10 11 12 13 14 main <<< val1: 6 val2: 10 main <<< dist1: 3 main <<< dist2: 3 main <<< lca = val: 9
If you recall the diagram, we should now be able to compute the distance between specified nodes as follows:
distance(7, 9) = distance(root, 7) + distance(root, 9) – 2 * distance(root, LCA) = (2 + 2) – (2 * 1) = 2
You can verify this result in the previous diagram
Now let’s generate the associated code:
// **** find the distance between the specified nodes ****
public int distNodes(Node root, int dist1, int dist2, Node lca) {
int dist = 0;
// **** ****
if ((dist1 != -1) &&
(dist2 != -1)) {
dist = dist1 + dist2 - (2 * distRootToVal(root, lca.getVal()));
}
// **** ****
return dist;
}
Our test code is now looking like:
/*
* Build a BST and find the distance between nodes.
*/
public static void main(String[] args) throws Exception {
// **** generate a range within the specified value ****
final int MAX_VAL = 16;
Random rand = new Random();
int[] range = {rand.nextInt(MAX_VAL) + 1, rand.nextInt(MAX_VAL) + 1};
System.out.println("main <<< range: [" + range[0] + ", " + range[1] + "]");
// **** generate an array of unique random integers in the specified range ****
int[] values = arrayWithUniqueValues(Math.min(range[0], range[1]),
Math.max(range[0], range[1]));
// **** use the random array to create a BST ****
BinaryTree tree = new BinaryTree();
for (int val : values) {
tree.insert(val);
}
// **** display the value of the root node****
System.out.println("main <<< root.val: " + tree.getRoot().getVal());
// **** display the BST (in order) ****
System.out.print("arrayWithUniqueValues <<< inorder: ");
tree.inorder(tree.getRoot());
System.out.println();
// **** generate two values to determine the distance ****
int val1 = Math.min(range[0], range[1]) + rand.nextInt(MAX_VAL / 3);
int val2 = Math.max(range[0], range[1]) - rand.nextInt(MAX_VAL / 3);
System.out.println("main <<< val1: " + val1 + " val2: " + val2);
// **** step 1: find distance from root to val1 ****
int dist1 = tree.distRootToVal(tree.getRoot(), val1);
System.out.println("main <<< dist1: " + dist1);
// **** step 2: find distance from root to val2 ****
int dist2 = tree.distRootToVal(tree.getRoot(), val2);
System.out.println("main <<< dist2: " + dist2); // **** step 3: find distance from root to LCA (Lowest Common Ancestor) **** Node lca = null; if ((dist1 >= 0) &&
(dist2 >= 0)) {
lca = tree.lca(tree.getRoot(), val1, val2, 0);
if (lca != null)
System.out.println("main <<< lca = " + lca.toString());
else
System.out.println("main <<< lca == null");
}
// **** step 4: find the distance between nodes ****
if (lca != null) {
int dist = tree.distNodes(tree.getRoot(), dist1, dist2, lca);
System.out.println("main <<< dist: " + dist);
}
}
A run and associate console screen capture follows:
main <<< range: [1, 12] arrayWithUniqueValues <<< from: 1 to: 12 arrayWithUniqueValues <<< n: 12 arrayWithUniqueValues <<< rarr: [11, 8, 5, 2, 7, 6, 9, 12, 4, 10, 3, 1] main <<< root.val: 11 arrayWithUniqueValues <<< inorder: 1 2 3 4 5 6 7 8 9 10 11 12 main <<< val1: 2 val2: 9 main <<< dist1: 3 main <<< dist2: 2 main <<< lca = val: 8 main <<< dist: 3
Seems like we are now able to put all together as illustrated:
package bst.canessa;
import java.security.SecureRandom;
import java.util.HashSet;
import java.util.Random;
/*
*
*/
public class Solution {
/*
* Generate an array of random numbers in the specified range.
*/
static int[] arrayWithUniqueValues(int from, int to) throws Exception {
System.out.println("arrayWithUniqueValues <<< from: " + from + " to: " + to);
// **** determine the number of integers to generate ****
int n = to - from + 1;
System.out.println("arrayWithUniqueValues <<< n: " + n);
// **** declare and populate an array with the numbers in ascending order ****
int arr[] = new int[n];
for (int i = 0; i < n; i++)
arr[i] = from + i;
// **** declare and populate the random array ****
int[] rarr = new int[n];
int x = n;
SecureRandom srand = new SecureRandom();
for (int i = 0; i < n; i++) {
int k = srand.nextInt(x);
rarr[i] = arr[k];
arr[k] = arr[x - 1];
x--;
}
// **** check if we have a duplicate random number ****
HashSet<Integer> set = new HashSet<Integer>();
for (int i = 0; i < rarr.length; i++)
if (!set.add(rarr[i]))
throw new Exception("arrayWithUniqueValues <<< duplicate: " + rarr[i]);
if (set.size() != n)
throw new Exception("arrayWithUniqueValues <<< set.size() != n: " + n);
// **** display the random array ****
System.out.print("arrayWithUniqueValues <<< rarr: [");
for (int i = 0; i < rarr.length; i++) {
System.out.print(rarr[i]);
if (i < rarr.length - 1)
System.out.print(", ");
}
System.out.println("]");
// **** return the random array ****
return rarr;
}
/*
* Build a BST and find the distance between nodes.
*/
public static void main(String[] args) throws Exception {
// **** generate a range within the specified value ****
final int MAX_VAL = 16;
Random rand = new Random();
int[] range = {rand.nextInt(MAX_VAL) + 1, rand.nextInt(MAX_VAL) + 1};
System.out.println("main <<< range: [" + range[0] + ", " + range[1] + "]");
// **** generate an array of unique random integers in the specified range ****
int[] values = arrayWithUniqueValues(Math.min(range[0], range[1]),
Math.max(range[0], range[1]));
// **** use the random array to create a BST ****
BinaryTree tree = new BinaryTree();
for (int val : values) {
tree.insert(val);
}
// **** display the value of the root node****
System.out.println("main <<< root.val: " + tree.getRoot().getVal());
// **** display the BST (in order) ****
System.out.print("arrayWithUniqueValues <<< inorder: ");
tree.inorder(tree.getRoot());
System.out.println();
// **** generate two values to determine the distance ****
int val1 = Math.min(range[0], range[1]) + rand.nextInt(MAX_VAL / 3);
int val2 = Math.max(range[0], range[1]) - rand.nextInt(MAX_VAL / 3);
System.out.println("main <<< val1: " + val1 + " val2: " + val2);
// **** step 1: find distance from root to val1 ****
int dist1 = tree.distRootToVal(tree.getRoot(), val1);
System.out.println("main <<< dist1: " + dist1);
// **** step 2: find distance from root to val2 ****
int dist2 = tree.distRootToVal(tree.getRoot(), val2);
System.out.println("main <<< dist2: " + dist2); // **** step 3: find distance from root to LCA (Lowest Common Ancestor) **** Node lca = null; if ((dist1 >= 0) &&
(dist2 >= 0)) {
lca = tree.lca(tree.getRoot(), val1, val2, 0);
if (lca != null)
System.out.println("main <<< lca = " + lca.toString());
else
System.out.println("main <<< lca == null");
}
// **** step 4: find the distance between nodes ****
if (lca != null) {
int dist = tree.distNodes(tree.getRoot(), dist1, dist2, lca);
System.out.println("main <<< dist: " + dist);
}
// **** putting all the steps together ****
int dist = tree.findDist(tree.getRoot(), val1, val2);
System.out.println("main <<< val1: " + val1 + " val2: " + val2 + " dist: " + dist);
}
}
The BinaryTree class code follows:
package bst.canessa;
/*
*
*/
public class BinaryTree {
Node root;
// **** constructor ****
public BinaryTree() {
this.root = null;
}
// **** ****
public Node getRoot() {
return this.root;
}
// **** insert node ****
public void insert(int val) {
if (this.root == null)
this.root = new Node(val);
else insert(this.root, val);
}
// **** insert node ****
private void insert(Node node, int val) {
// **** insert to the left ****
if (val < node.getVal()) { if (node.getLeftChild() == null) { node.setLeftChild(new Node(val)); } else { insert(node.getLeftChild(), val); } } // **** insert to the right **** else { if (node.getRightChild() == null) { node.setRightChild(new Node(val)); } else { insert(node.getRightChild(), val); } } } // **** in order traversal **** void inorder(Node node) { // **** base case (to end recursion) **** if (node == null) return; // **** **** inorder(node.getLeftChild()); System.out.print(node.getVal() + " "); inorder(node.getRightChild()); } // **** find distance from root to the node with the specified value **** public int distRootToVal(Node root, int val) { // **** base case (to end recursion) **** if (root == null) return -1; // **** initialize the distance **** int dist = -1; // **** check if value is in this node or in one of it's children **** if ((root.getVal() == val) || (dist = distRootToVal(root.getLeftChild(), val)) >= 0 ||
(dist = distRootToVal(root.getRightChild(), val)) >= 0)
return dist + 1;
// **** ****
return dist;
}
// **** find lca (Lowest Common Ancestor) ****
public Node lca(Node root, int val1, int val2, int rootDist) {
// **** base case (to end recursion) ****
if (root == null)
return null;
// **** ****
if (root.getVal() == val1)
return root;
if (root.getVal() == val2)
return root;
// **** ****
Node leftLCA = lca(root.getLeftChild(), val1, val2, rootDist + 1);
Node rightLCA = lca(root.getRightChild(), val1, val2, rootDist + 1);
// **** ****
if ((leftLCA != null) &&
(rightLCA != null))
return root;
// **** ****
return (leftLCA != null) ? leftLCA : rightLCA;
}
// **** find the distance between the specified nodes ****
public int distNodes(Node root, int dist1, int dist2, Node lca) {
int dist = 0;
// **** ****
if ((dist1 != -1) &&
(dist2 != -1)) {
dist = dist1 + dist2 - (2 * distRootToVal(root, lca.getVal()));
}
// **** ****
return dist;
}
// **** find distance between nodes in a BST ****
public int findDist(Node root, int val1, int val2) {
int dist = -1;
// **** step 1: find distance from root to val1 ****
int dist1 = distRootToVal(root, val1);
if (dist1 == -1)
return -1;
System.out.println("findDist <<< dist1: " + dist1);
// **** step 2: find distance from root to val2 ****
int dist2 = distRootToVal(root, val2);
if (dist2 == -1)
return -1;
System.out.println("findDist <<< dist2: " + dist2);
// **** step 3: find distance from root to LCA (Lowest Common Ancestor) ****
Node lca = lca(root, val1, val2, 0);
if (lca == null)
return -1;
System.out.println("findDist <<< lca = " + lca.toString());
// **** step 4: find the distance between nodes ****
dist = distNodes(root, dist1, dist2, lca);
System.out.println("findDist <<< dist: " + dist);
// **** ****
return dist;
}
}
And a last screen capture:
main <<< range: [9, 2] arrayWithUniqueValues <<< from: 2 to: 9 arrayWithUniqueValues <<< n: 8 arrayWithUniqueValues <<< rarr: [7, 3, 6, 8, 4, 5, 9, 2] main <<< root.val: 7 arrayWithUniqueValues <<< inorder: 2 3 4 5 6 7 8 9 main <<< val1: 2 val2: 5 main <<< dist1: 2 main <<< dist2: 4 main <<< lca = val: 3 main <<< dist: 4 findDist <<< dist1: 2 findDist <<< dist2: 4 findDist <<< lca = val: 3 findDist <<< dist: 4 main <<< val1: 2 val2: 5 dist: 4
I was going to implement a method to print the BST but decided to leave that for another time. I do search the Internet for ideas. I do not like to add code if I do not understand it and if needed modify it to fit the particular requirements. That said, I did find some code to print a binary tree in Stack Overflow. I just felt that I wanted to implement the method myself. Keep in mind that I use this blog to better understand technical items. I believe that if you are not able to describe something, you do not know it well enough (Richard Feynman)
As usual, if you have comments or questions with this or any other post in this blog, please leave me a note bellow.
Keep on learning;
John
Follow me on Twitter: @john_canessa