Things might be getting somewhat more complex with the COVID-19 pandemic that started in Wuhan, China. The CDC has been posting articles stating that individuals, who have recovered from COVID-19, may be prone to reinfection after three months. The theory of herd immunity, without a vaccine, goes out the door.
On a side note, people in the city of Wuhan, China have been celebrating that coronavirus is receding (there is no way to find out with data what is actually happening there) in their city with a massive water park party. The Chinese Communist Party does not seem to accept responsibility for the 800,000 deaths globally which they allowed to happen and are taking advantage of it in different ways.
I just finished updating a storage server CLI so it returns data in JSON format. All appears to be fine. Decided to take a few minutes and generate this post.
The idea is relative similar to what I did in Lowest Common Ancestor in Binary Search Tree. The difference is that in this case we are dealing with a generic binary tree. This implies that the values associated to nodes are in no specific order like in a Binary Search Tree (BST).
I found on LeetCode the 236. Lowest Common Ancestor of a Binary Tree problem. I decided to tackle it in Java using the VSCode IDE on a Windows 10 computer. Of course the IDE and the platform should be of no concern to you.
If interested, take a look at the requirements at the LeetCode site. The site has two examples using the same binary tree. BTW you only need to develop the function / method to find the lowest common ancestor (LCA). The scaffolding and utility code to build the binary tree are not shown.
As I have mentioned many times, I enjoy developing code and like to use a modified (not to say the essence of) Test Driven Development approach. When I was growing up, my dad who was born in Genoa, Italy, told me many 
times that when I grew up I did not have to build an entire car. I should build one or two components, but they should be the best components available. Doing that requires attention to detail, constant learning, and experience which comes with time. When I apply the concept of TDD and the advice from my dad I came up with a top down approach to develop software. If you are interested in the approach, I can write a post for this blog.
The first this we need for the test scaffolding is to process the data presented by LeetCode. The data can be organized in different ways given that it will not affect the final function that we need to develop.
3 5 1 6 2 0 8 null null 7 4
7
5 1
6 2
7 4
0 8
6 8
5 4
4 5
3
5 1
6 2 0 8
7 4
main <<< (5,1) lca: 3
main <<< (6,2) lca: 5
main <<< (7,4) lca: 2
main <<< (0,8) lca: 1
main <<< (6,8) lca: 3
main <<< (5,4) lca: 5
main <<< (4,5) lca: 5
If you compare the data provided by LeetCode to the first line of the screen capture, you should notice we have a match. LeetCode also provides a diagram of the resulting binary tree so I will skip reproducing it here. We need to populate a binary tree in level order. The two null values should skip the node with value 6 and should apply 7 and 4 as children of node with value 2. This has nothing to do with the actual problem, but I like to develop software with the tools I use. In addition, while generating scaffolds you have a chance to learn something.
The second line indicates the number of queries we will perform in the binary 
tree. In our case we have 7 queries. Each query is in a separate line. Each query consists of the values of node p and q as stated in the problem.
After loading the binary tree I displayed it. The first two children in level four for the first node are null.
We then generate the LCA for each pair of nodes. Using the diagram you can verify that the code seems to work. In addition I submitted my code for the required method / function and it was accepted.
/**
* Test scaffolding.
*/
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read the node values and place them in an array of strings ****
String strVal[] = sc.nextLine().split(" ");
// **** root for the binary tree ****
TreeNode root = null;
// **** populate the binary tree ****
root = insertLevelNode(strVal, root, 0);
// **** print the binary tree in breath-first order ****
levelOrderTraversal(root);
// **** get the number of queries ****
int m = Integer.parseInt(sc.nextLine());
// ***** loop once per query ****
for (int i = 0; i < m; i++) {
// **** read p and q ****
String[] pAndQ = sc.nextLine().split(" ");
// **** convert to integer ****
int pVal = Integer.parseInt(pAndQ[0]);
// **** convert to integer ****
int qVal = Integer.parseInt(pAndQ[1]);
// **** find node p ****
TreeNode p = find(root, pVal);
// **** find node q ****
TreeNode q = find(root, qVal);
// **** find the LCA of p and q ****
TreeNode lca = lowestCommonAncestor(root, p, q);
// **** display the LCA ****
System.out.println("main <<< (" + pVal + "," + qVal + ") lca: " + lca.val);
// // **** find the LCA of p and q (second attempt; ended being the same as previous) ****
// lca = lcaPostOrder(root, p, q);
// // **** display the LCA ****
// System.out.println("main <<< (" + pVal + "," + qVal + ") lca: " + lca.val);
}
// **** close scanner ****
sc.close();
}
This is the code for the test scaffolding. We open a scanner and read the line with the node values and split them into an array of strings. I figured this would work to handle the null values. We then populate the binary tree using the insertLevelNode() function. To get the warm and fuzzy feeling that the tree was built correctly we display the values of the nodes using a level order approach.
With the number of queries we need to perform at hand, we loop once per query, extract the values for p and q, find the associated nodes in the tree, and use them to find the LCA node. We display the value of the node.
When done, we close the scanner. This is good practice even though in this case the program exists and the scanner will be automatically closed.
/**
* Auxiliary class to build the binary tree.
*/
class TreeNode {
// **** members ****
int val;
TreeNode left;
TreeNode right;
// **** constructor ****
TreeNode(int x) {
val = x;
}
}
This is the same class used by LeetCode to represent nodes in the binary tree. We will use the same class and will not add methods or members to it.
/**
* Insert nodes into a binary tree in level order.
* This function is recursive.
*/
static TreeNode insertLevelNode(String[] arr, TreeNode root, int i) {
// **** recursion base case ****
if (i < arr.length) {
// **** allocate element (if needed) ****
if (!arr[i].equals("null")) {
TreeNode temp = new TreeNode(Integer.parseInt(arr[i]));
root = temp;
} else {
return null;
}
// **** insert left child ****
root.left = insertLevelNode(arr, root.left, 2 * i + 1);
// **** insert right child ****
root.right = insertLevelNode(arr, root.right, 2 * i + 2);
}
// **** ****
return root;
}
This function is used to recursively insert nodes into the binary tree. We insert a null node when a node does not have a child. We do so by traversing the list of values in the array, offsetting to the proper node in the binary tree, and then inserting the value (or null) as a child. This code is not required for the solution to the problem. This function is used by the test scaffold only.
/**
* Perform a level order traversal of the binary tree.
*/
static void levelOrderTraversal (TreeNode root) {
// **** ****
List<TreeNode> currentQ = new LinkedList<TreeNode>();
List<TreeNode> nextQ = new LinkedList<TreeNode>();
// **** start the process ****
currentQ.add(root);
// **** traverse all levels ****
while (!currentQ.isEmpty()) {
// **** start with the leftmost node in this level ****
TreeNode node = currentQ.remove(0);
// **** ****
if (node != null) {
// **** print current node ****
System.out.print(node.val + " ");
// **** add left child to the next queue ****
if (node.left != null)
nextQ.add(node.left);
else
nextQ.add(null);
// **** add the right child to the next queue ****
if (node.right != null)
nextQ.add(node.right);
else
nextQ.add(null);
} else {
// **** print null object ****
System.out.print(" ");
}
// **** check for the then end of this level ****
if (currentQ.isEmpty()) {
// **** print line separator (end of this level) ****
System.out.println();
// **** swap lists ****
currentQ = nextQ;
nextQ = new LinkedList<TreeNode>();
}
}
}
This function is used to perform a level order traversal of a binary tree. We use two lists. The first one is used to process a level. The second one is used to build a level. The lists are interchanged and the process repeats.
The loop removes and adds nodes to the lists and prints the values of the nodes as it goes. When the currentQ list is empty, it swaps the lists and the loop continues. Eventually the current list will be empty and the process ends.
/**
* Find the node with the specified value.
* Initialization for recursive call.
*/
static TreeNode find(TreeNode root, int val) {
Stack<TreeNode> stack = new Stack<TreeNode>();
find(root, val, stack);
if (!stack.empty())
return stack.pop();
else
return null;
}
This function is used to find a node in the binary tree. We specify the root of the tree and the value of the node.
/**
* Find the node with the specified value.
* This is a recursive function.
*/
static void find(TreeNode root, int val, Stack<TreeNode> stack) {
// **** ****
if (root == null)
return;
// **** find on left child ****
find(root.left, val, stack);
// **** ****
if ((root != null) && (root.val == val)) {
stack.push(root);
}
// **** find on right child ****
find(root.right, val, stack);
}
This function is called by the non-recursive method with the same name. Node we are passing a stack. The stack is used to store the node that we are looking for.
/**
* Find the LCA.
* Recursive method.
*/
static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// **** check if we are done ****
if ((root == null) || (root == p) || (root == q))
return root;
// **** traverse the left tree ****
TreeNode left = lowestCommonAncestor(root.left, p, q);
// **** traverse the right tree ****
TreeNode right = lowestCommonAncestor(root.right, p, q);
// **** return the root node as the LCA (p and q in this tree) ****
if ((left != null) && (right != null))
return root;
// **** return the left OR the right node as the LCA ****
return left != null ? left : right;
}
This represents the solution for this problem. This is a simplification of what I used to understand and explore a solution.
/**
* Post order of binary tree traversal.
* Recursive method.
*/
static TreeNode lcaPostOrder(TreeNode root, TreeNode p, TreeNode q) {
// **** end case ****
if ((root == null) || (root == p) || (root == q))
return root;
// **** visit the left child ****
TreeNode left = lcaPostOrder(root.left, p, q);
// **** visit the right child ****
TreeNode right = lcaPostOrder(root.right, p, q);
// **** p and q in the current root of the binary tree ****
if ((left != null) && (right!= null))
return root;
// **** p or q found but not both ****
if (left != null)
return left;
else
return right;
}
This is the code I used (with many edits) to get to a solution. The idea is to traverse the binary tree using a post order traversal. We start with the end case. After the end case we check the left tree and then the right.
We then decide what to return. The idea is that if we find p and q using the same root, both are descendants of the current root node. If that is not the case, we return the node (left or right) in which p or q was found. In this case the nodes of interest have different parents (roots).
I checked multiple on-line articles when working on the solution. It takes some time to fully come to grip to what and most important how we need to structure the code.
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,625 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
Twitter: @john_canessa