Good morning. Hope your day has started on the right note. A couple weeks ago, the extended weather forecast for the Twin Cities of Minneapolis and St. Paul had the high temperatures in the low 60’s and 70’s. This week we have experienced high temperatures in the mid 80’s. It seems that with the power of the cloud, large models that make use of AI, and tons of data, accuracy predicting the weather is still out of our reach.
I have a lifetime friend. Our friendship started in elementary school. Now with the COVID-19 (or Chinese flu) pandemic we connect using Skype on Friday at 07:00 AM. By 08:00 AM we both start or work day.
Today we discussed two set of news. In Peru the number of deaths attributed 
to COVID-19 is consistently dropping. Keep in mind that social distancing and lockdowns are not strictly enforced. It appears that with time physicians at healthcare facilities, due to trial and error and on-line education, have figured out treatments that work. In addition, the most vulnerable population has been dramatically reduced. That is not good but it seems to be an obvious reality. Hospitals have open beds in the ICUs. Private hospitals are starting to advertise to invite patients for non-COVID treatments and procedures.
The second news was a study performed in South Africa. Apparently the mostly black population has experienced considerably less deaths than in the USA. Of course, the demographics of both countries are different but when taking the percentages of blacks and Hispanics in these two countries, we should be able to conclude that perhaps something being done in South Africa 
is reducing COVID-19 mortality.
I like to take all news with a grain (perhaps a block) of salt. This is especially true with the presidential elections so close. It seems that in the USA most news are fake or adjusted to the political orientation of the publishing organization.
Following is some data to consider:
Current population Peru: 31.99 M
Current population South Africa: 57.78 M
Current population USA: 328.2 M
COVID-19 deaths yesterday Peru: 68
COVID-19 deaths yesterday South Africa: 77
COVID-19 deaths yesterday USA: 826
If the data is accurate, the USA is not doing that well. Perhaps our healthcare system needs to be revamped.
OK, let’s get to the main topic for this post. I selected an easy problem from 
LeetCode that makes use of binary trees. The reason is that in previous posts I have been showing and discussing the test scaffoldings that I put together to develop the solution on my computers. In the case of binary trees it takes a lot of space and words.
Today, I have decided to keep the post relatively short. Will just cover the main() function of the test scaffolding. If interested in the rest of the code associated with the scaffolding, please visit my GitHub repository.
The problem for the day comes from LeetCode. It is problem 104 Maximum Depth of Binary Tree.
A binary tree is a data structure that has two child nodes. An instance may have none, one or two child nodes. The value of a node does not dictate the position in the binary tree.
Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Note: A leaf is a node with no children.
The requirements are simply described by LeetCode. We need to find the longest path from the root to the farthest down leaf node. The description is quite complete for the requirements.
Since we need to deal with the leaf nodes, the problem seems a good candidate for an in-order tree traversal.
We will implement a solution using the Java programming language. In my case I used VSCode as my IDE running on a Windows 10 machine. Please note that the IDE and the operating system are out of the scope of the solution. The solution should work on any platform supporting the JAVA VM.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
}
}
The description of the data structure used to represent nodes in the binary tree is provided as a comment by LeetCode. We are supposed to fill in the maxDepth() function.
1 main <<< inOrder: 1 main <<< maxDepth: 1 1,2,3 main <<< inOrder: 2 1 3 main <<< maxDepth: 2 3,9,20,null,null,15,7 main <<< inOrder: 9 3 15 20 7 main <<< maxDepth: 3
Based on what is provided by the single example, in our test scaffolding which is not part of the solution, we need to get breadth first data and populate a binary tree. Of course we could just manually populate the binary tree. The drawback of such approach is that we would have to write custom code for each example. Not a good idea.
In our case we populate different binary trees and compute the maximum depth. After building a binary tree we make an in-order tree traversal to make sure the binary tree was properly built. We then seem to call the maxDepth() function and display the result. The first binary tree has a depth of q. The second a depth of 2 and the last example which happens to be the one provided by LeetCode, has a maximum depth of 3.
This would be a good time to stop and figure out how to solve the problem. When you are ready please come back…
… OK, let’s continue.
/**
* Test scaffolding
*/
public static void main(String[] args) {
// **** BT root ****
TreeNode root = null;
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read data for BT (in level order) ****
String[] arr = sc.nextLine().split(",");
// **** close scanner ****
sc.close();
// **** populate the binary tree ****
root = populateBT(arr);
// ???? display the binary tree ????
System.out.println("main <<< inOrder: ");
inOrder(root);
System.out.println();
// **** find and display the depth of the BT ****
System.out.println("main <<< maxDepth: " + maxDepth(root));
}
This is the test scaffolding that I used to solve the problem on my computer. It is not related to the actual solution. The idea is to read the line describing the binary tree, populating it, checking all is well by performing an in-order traversal, and then calling the maxDepth() function and displaying the result.
As you can see the populateBT() function is used to populate the binary tree. I will not cover in this post how it works. You can always find previous posts i.e., Count Good Nodes in Binary Tree in this blog which cover in detail how the binary tree is populated using this function.
/**
* Given a binary tree, find its maximum depth.
* Recursive function O(n).
*/
static int maxDepth(TreeNode root) {
// **** base condition ****
if (root == null)
return 0;
// **** initialize the BT max depth ****
int depth = 0;
// **** visit left node ****
depth = Math.max(depth, maxDepth(root.left) + 1);
// **** visit right node ****
depth = Math.max(depth, maxDepth(root.right) + 1);
// **** return the max depth ****
return depth;
}
This is the function of interest. When I was done I copied the body and pasted it in the LeetCode web site. The solution was accepted.
The solution is recursive. We need a point in which we can stop. This is called the base condition. In our case, it would make sense to stop at a null (leaf) node. At that point we can return a 0 to start the count backwards (up).
We then initialize the value we are going to return.
The following two lines implement recursion. In our case we need to traverse the left and the right child to count the depth. The code is almost identical for both children. We need to get the maximum value of the sub tree starting at the child node. The max value is between what we have so far and the depth for the child tree we just traversed. If in doubt, please take a few moments with a piece of paper and pen and make sure you are able to follow the process on the left node. The one on the right node is identical with the exception that we traverse the right tree.
The idea is very similar on how an in-order tree traversal is implemented. You can always look at the code for the inOrder() function which is part of the test scaffolding; not the solution.
he 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 2663 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
Twitter: @john_canessa