It is a beautiful sunny summer day in the Twin Cities of Minneapolis and St. Paul. The high temperature for today in the city I live is forecasted to be 83 F. I prefer high temperatures in the range of 75 F to 80 F, but 83 F will have to do.
Yesterday I spent a few hours in front of my computers. My wife left early with a friend to go walking and shopping. My wife got back shortly after 11:00 AM. We made some potatoes with veggies in the grill using a cast iron pan. We always add some pepper, salt and a splash of oil with a high smoke point (i.e., avocado or peanut).
Yesterday I ordered from Amazon Prime a couple spindles of butcher string. The second one was for my son who is also into cooking meats in the grill and smoker. We both ran out of it at the same time. I cut and cleaned a hefty
piece from a knuckle that I had pulled out from the outdoor freezer a couple days ago. I cleaned the beef but the delivery of the butcher string was via USPS which delivers mail to our area between 03:00 PM to 04:00 PM. Too late for lunch!
I put the veggies in the pan and cranked up both burners in the grill as high as they go. My wife and I sat around the grill sipping some Stella Artois beer while pecking at some capocollo / capicola ham dipped in mustard over some sesame seed crackers.
When the temperature in the grill was around 550 F (should have waited for over 600 F) we placed the cut of beef which was covered with salt and pepper and some olive oil. We let it cook for about 10 minutes. Then we flipped the meat and let it cook for another 10 minutes. When the time was up, we turned 
off the grill and scooped the veggies from the cast iron pan to a glass bowl. The steak (around 5 lbs) was moved to a platter to let it rest for about 5 minutes before cutting it into slices.
After lunch we rested for a few and then made from scratch a batch of cream puffs and associated pastry cream. When all was done (we are talking about 05:30 PM), we headed to our son’s house. It was his birthday so we took some cream puffs. We made it back home around 09:00 PM. It was a long day for us.
By the way, I did receive the cooking twine via USPS Saturday afternoon.
Yesterday morning I spent time solving LeetCode problem 235 Lowest Common Ancestor of a Binary Search Tree.
Before we get into the actual code, we need to make sure we understand what a Binary Tree is, and the differences from a Binary Search Tree. Both trees are 
binary trees because each node may have up to two children (hence the name binary). The difference is that in a BST the left branch of any node will hold values that are all lower that the value of the node. Of course, the values on the right will all be higher than the value of a node. This holds true for all nodes.
If you are interested in this problem, please visit the LeetCode web site and read the requirements. They are quite simple to articulate. Given a BST and two nodes, find the lowest common ancestor for them.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int x) {
val = x;
}
}
The recommended class TreeNode will be used to represent the nodes in the BST. The class is quite simple. It contains a value for the node and two children. It also contains a constructor. For starters it looks fine. Note that we should not add functionality to it unless we use it for testing purpose only. If we add methods and fields when we submit the code it will fail.
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
}
The requirements in class Solution seem to contain at least a single method named lowestCommonAncestor() with three arguments. We can select any node as a root and a couple other nodes. The method should return the LCA node.
Now let’s run a test of our completed code. Note that initially the test would read and process the arguments and will return a default answer. After working on the lowestCommonAncestor() function we should expect correct answers. This is the essence of the Test Driven Approach (TDD). It does not require unit testing code. That is typically a task for the next developer that will be making sure the code works as expected. If you have questions regarding this approach, please send me your comments.
9 6 2 8 0 4 7 9 3 5 7 2 8 2 4 2 5 3 9 0 5 7 7 1 1 main <<< n: 9 main <<< inOrder: 0 2 3 4 5 6 7 8 9 main <<< m: 7 main <<< lca.val: 6 2 2 6 2 7
LeetCode does not provide testing scaffolding that you can see. You have to develop your code on the site. I always develop code using the IDEs I am familiar and configure it the way I like. I believe all developers work this way.
The first line of the testing scaffold requests a number (n) of elements for the BST. In this case n is equal to 9. The following line contains the integer value of the BST nodes. The third line contains the number of queries (m) we will perform. In this example we will issue 7 queries. The queries consist of the values for the two nodes. Based on the requirements and the prototype for the function we need to implement the test scaffolding seems to be adequate.
Note that most of the queries are using values for existing nodes in the BST and they are different. We also check the conditions where the two nodes are the same, or if we pass non-existing nodes. I guess I could have checked the two combinations of existing and non-existing nodes (i.e., 1, 6 and 6, 1). Such conditions would be great unit tests which a different developer would write. Of course if the code is rejected, I will have to address the issue and return it for additional testing.
The test scaffolding displays the number of elements specified and then performs an in-order traversal of the BST. This is done just to make sure we did not make a mistake loading the BST. The numbers are in order so all is well so far.
We have specified 7 queries. The results are for only 6. The reason is that the last query is not possible. I should go back and display something when such condition is encountered. If this would be production software I would not accept it. I went back to the code and updated it to display a ‘?’ when we encounter a value not included in the BST.
/**
* Definition of binary tree node.
*/
class TreeNode {
// **** ****
int val;
TreeNode left;
TreeNode right;
// **** ****
TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
The updated TreeNode class as I declared in my Solution. Note I did not add members or methods.
/**
* Test scaffolding.
*/
public static void main(String[] args) {
// *** define the root of the binary tree ****
TreeNode root = null;
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read the number of nodes ****
int n = sc.nextInt();
// ???? ????
System.out.println("main <<< n: " + n);
// **** read the n values and populate the BST ****
for (int i = 0; i < n; i++) {
// **** read the value ****
int x = sc.nextInt();
// **** insert this value into the BST ****
root = insert(root, x);
}
// **** in-order traversal of the BST ****
System.out.print("main <<< inOrder: ");
inOrder(root);
System.out.println();
// **** read the number of queries ****
int m = sc.nextInt();
// ???? ????
System.out.println("main <<< m: " + m);
// **** start output ****
System.out.print("main <<< lca.val: ");
// **** loop reading and processing each query ****
for (int i = 0; i < m; i++) {
// **** read the value for p ****
int pVal = sc.nextInt();
// **** read the value for q ****
int qVal = sc.nextInt();
// **** get the p node ****
TreeNode p = find(root, pVal);
// **** check if value was not found ****
if (p == null) {
System.out.print("? ");
continue;
}
// **** get the q node ****
TreeNode q = find(root, qVal);
// **** check if value was not found ****
if (q == null) {
System.out.print("? ");
continue;
}
// **** determine the lca for p and q ****
TreeNode lca = lowestCommonAncestor(root, p, q);
// TreeNode lca = lcaIterative(root, p, q);
// **** display this result ****
System.out.print(lca.val + " ");
}
// **** complete output ****
System.out.println();
// **** close scanner ****
sc.close();
}
This is the test scaffolding I wrote for this problem. For me solving problems is getting them right and as efficient as needed to be accepted. In case of production code, I spend the additional time to improve the efficiency within limits. In more than an occasion I have deleted the code and started a different fresh approach. Note that in general, the testing scaffolding I write (which in most cases it is not provided by a third party) would be applicable, so the effort is not wasted.
We define our BST. We open a scanner and start reading the data we need to populate the BST. Values are added one at a time using the static method insert. We will see it in a minute.
After the BST is ready, we display it using the inOrder() method. The values of the BST should appear in an ascending order. We then get the number of queries (m) and for each query we read the p and q values. Note that we check is the values are not in the BST and display a “? “, instead of just skipping to the next query without an indication.
We are now ready to make the call to the lowestCommonAncestor() function required by this problem. We get the returned LCA and display its value.
Note that commented in the code is the lcaIterative() function. This is just an added bonus. When you develop a recursive function / method, you should always be able to reproduce it using loops. The advantage of the loops is that they consume a minimum amount of stack (single call). When you have deep recursive calls, your program will require large amount of stack space.
/**
* Insert a node with the specified value into the the BST.
* Recursive method.
*/
static TreeNode insert(TreeNode root, int val) {
// **** ****
if (root == null) {
return new TreeNode(val);
} else {
// **** ****
if (val <= root.val)
root.left = insert(root.left, val);
else
root.right = insert(root.right, val);
// **** ****
return root;
}
}
The insert() function is a recursive helper function for our test scaffolding. It checks if the root is not available. In such case, it creates a new node and returns. Otherwise the code traverses the left child or the right child as needed. When it reaches a leaf node, it will create a new node with the specified value.
/**
* Display the nodes performing an in-order BST traversal.
* This is a recursive function.
*/
static void inOrder(TreeNode root) {
// **** check if we are done ****
if (root == null)
return;
// **** visit the left child ****
inOrder(root.left);
// **** display the value of this node ****
System.out.print(root.val + " ");
// **** visit the right child ****
inOrder(root.right);
}
The inOrder() function is also a recursive helper function for our test scaffolding. It checks if the root is null and returns. Otherwise it visits the next left node. When it continues it displays the value of the current root. It then visits the right child. The net effect is to display the nodes in the BST in ascending order. In this example we use it to visually inspect if the BST was built in order. We could place the values in a data structure, and then, using a loop, verify they are in ascending order.
/**
* Find the node with the specified value.
* This is a recursive function.
*/
static TreeNode find(TreeNode root, int val) {
// **** check if node was not found ****
if (root == null)
return null;
// **** check if we found the desired node ****
if (root.val == val)
return root;
// **** select next node ****
if (val <= root.val)
return find(root.left, val);
else
return find(root.right, val);
}
We need to provide as arguments to the function the actual nodes with the values p and q. The find recursive helper method achieves that. If the value is not found the function returns null. If the value is found the proper node is returned. If the value is not found yet, it selects the left or the right node and proceeds. This is possible because we are dealing with a BST.
/**
* Find the LCA of the specified nodes starting at the specifieed root.
* Iterative method.
*/
static TreeNode lcaIterative(TreeNode root, TreeNode p, TreeNode q) {
// **** loop until lca is found ****
while ( ((p.val < root.val) && (q.val < root.val)) ||
((p.val > root.val) && (q.val > root.val))) {
// **** traverse left ****
if ((p.val < root.val) && (q.val < root.val))
root = root.left;
// **** traverse right****
if ((p.val > root.val) && (q.val > root.val))
root = root.right;
}
// **** return lca ****
return root;
}
This is a possible solution for the problem implemented iteratively. We loop until the condition is not met. On each pass we update the root based on the values of p and q. In the first condition we move left and in the second we move right. Finally we return the value of the LCA which could be null.
/**
* Find the LCA of the specified nodes starting at the specifieed root.
* Recursive method.
*/
static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// **** traverse left ****
if ((p.val < root.val) && (q.val < root.val))
return lowestCommonAncestor(root.left, p, q);
// **** traverse right ****
if ((p.val > root.val) && (q.val > root.val))
return lowestCommonAncestor(root.right, p, q);
// **** return lca ****
return root;
}
This method is a possible solution to the problem. It has been implemented with a recursive approach. In a nutshell it uses less lines of code, but more stack memory. Because it is more elegant, I submitted this last code as my solution to the LeetCode problem.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address: john.canessa@gmail.com. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!
One last thing, many thanks to all 1,617 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
Twitter: @john_canessa