It is Monday morning. I got up earlier to finish the code and this post. Hope to be done before 06:00 AM. Today is my wife’s birthday. She is an evening person. Every morning I get up, fix breakfast, and then wake her up.
This year due to the COVID-19 pandemic (thanks China) we have not planned a celebration. Dates tend to shift by a day on non-leap years. Yesterday I received a message with Google photos that we took on 
yesterday’s date several years ago. Last year for her birthday we were with some family, friends in Rome, Italy. In the evening we all had a nice dinner and walked to the Fontana di Trevi and tossed three coins. That was a nice way to close the day. We like Italy and have been there many times. Perhaps next year things will be back to the new normal and will be able to celebrate once again in Rome.
Yesterday I selected LeetCode problem 617. Merge Two Binary Trees. As usual I generated the test scaffolding. I like doing so because of the freedom of checking things while developing the solution.
Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree. Note: The merging process must start from the root nodes of both trees.
The requirements from LeetCode are well defined. You get two binary trees. The idea is to merge both trees into one. If both trees have a node in the same position, you need to add their values. If only one tree has a node, you need to use the value of that node. Finally is both trees lack a node at a particular position, then we need to put a null node.
For this problem I will use the Java programming language and the VSCode IDE running on a Windows 10 machine. Of course you can use any IDE or choice or just solve the problem on the LeetCode site. The OS should be irrelevant.
/**
* 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 TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
}
}
We need to solve the problem using the TreeNode class. Our solution needs as an entry point the mergeTrees() function.
1,3,2,5 2,1,3,null,4,null,7 main <<< t1: 1 3 2 5 null null null main <<< t2: 2 1 3 null 4 null 7 mergeTrees <<< m.val: 3 mergeTrees <<< m.val: 4 mergeTrees <<< m.val: 5 mergeTrees <<< m.val: 4 mergeTrees <<< m.val: 5 mergeTrees <<< m.val: null mergeTrees <<< m.val: 7 main <<< m: 3 4 5 5 4 null 7 main <<< t1: 1 3 2 5 null null null
The test scaffolding expects two lines. Each line describes a binary tree which we should merge. The test scaffolding displays the first tree followed by the second one. This should help us verify that the data generated the trees we desire. If you compare the output with the trees in the example provided by LeetCode, they match.
It appears that the mergeTrees() function displays some numbers. You can verify that the numbers match the values for the merged tree. If you have doubts, please check the diagrams for the input and output (merged) trees in the LeetCode web site.
Our test scaffolding then displays the merged binary tree in level order. That seems to match the expected example result.
For some reason we decided to display the first tree a second time. The reason will become apparent as we experiment with the solution.
/**
* Definition for a binary tree node.
*/
class TreeNode {
// **** class members ****
int val;
TreeNode left;
TreeNode right;
// **** constructors ****
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
// **** ****
@Override
public String toString() {
return "" + this.val;
}
}
I could have skipped the TreeNode class with the rest of the scaffolding support code, but I did not. Please note that it matches the information provided by LeetCode. I added (but is not used) the toString() method to the class.
/**
* Test scaffolding
*/
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read data for tree 1 ****
String[] arr1 = sc.nextLine().split(",");
// **** populate tree 1 ****
TreeNode t1 = populateBT(arr1);
// **** done with this array ****
arr1 = null;
// ???? BFS traversal of t1 to check if all is well so far ????
System.out.println("main <<< t1: ");
System.out.print(bfsTraversal(t1) + "\n");
// **** read data for tree 2 ****
String[] arr2 = sc.nextLine().split(",");
// **** close scanner ****
sc.close();
// **** populate tree 2 ****
TreeNode t2 = populateBT(arr2);
// **** done with this array ****
arr2 = null;
// ???? BFS traversal of t1 to check if all is well so far ????
System.out.println("main <<< t2: ");
System.out.print(bfsTraversal(t2) + "\n");
// **** merge treee****
TreeNode m = mergeTrees(t1, t2);
// ???? BFS traversal of merged tree to check if all is well ????
System.out.println("main <<< m: ");
System.out.print(bfsTraversal(m) + "\n");
// ???? ????
System.out.println("main <<< t1: ");
System.out.print(bfsTraversal(t1) + "\n");
}
The test scaffolding is not part of the solution. It is needed if you wish to develop the solution on your computer of choice.
We open a scanner, read the data in level order for the two binary trees, display the trees and then call the mergeTrees() function. It returns a new tree which we display. We also display the first input tree.
I will not cover in any additional detail the test scaffolding. All the code for it is on my GitHub repository. If interested please visit GitHub.
/**
* Merge two binary trees.
* Use an in-order traversal model.
* Recursive method.
* Returns a new merged binaty tree.
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 39 MB, less than 99.82% of Java online submissions.
* Runtime O(n)
*/
static TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
// **** base case(s) ****
if ((t1 == null) && (t2 == null)) {
// ???? ????
System.out.println("mergeTrees <<< m.val: null");
// **** both nodes are null ****
return null;
}
if (t1 == null) {
// ???? ????
System.out.println("mergeTrees <<< m.val: " + t2.val);
// **** use node from t2 ****
return t2;
}
if (t2 == null) {
// ???? ????
System.out.println("mergeTrees <<< m.val: " + t1.val);
// **** use node from t1 ****
return t1;
}
// *** both nodes are available (sum their values) ****
TreeNode m = new TreeNode(t1.val + t2.val);
// ???? ????
System.out.println("mergeTrees <<< m.val: " + m.val);
// **** traverse left children ****
m.left = mergeTrees(t1.left, t2.left);
// **** traverse right children ****
m.right = mergeTrees(t1.right, t2.right);
// **** returned merged tree ****
return m;
}
In the header comments for the function it states that it returns a new merged tree. We could have returned the merged tree by updating the contents of the first tree. That would have used less memory and perhaps be slightly more efficient, but since the requirements do not specify if we may or may not modify one of the trees, it is always better to not induce side problems. If it would be production code, perhaps the trees could have been 
used later in the program and we just changed one of them. That could induce a subtle problem especially if the code is updated by a different developer sometime in the distant future.
Please disregard the print statements. I just used them for debugging and in production code, perhaps to log some key information to our logging system.
We are using a pre-order traversal approach. We could have used a breadth first search, but that would have taken additional resources and would not have been as simple as the first.
We first check if both or only one of the nodes is null. In the first case we need to return a null node. The other two cases return the non-null node from the trees.
When we get to the visiting of the node part in the pre-order algorithm, we could just modify the first of the second tree. In this case we create a new node and assign the sum of the values of the input nodes.
We then traverse the left and right children using recursion. The results are used to update the left and right children of our merged node. When done, we returned the merged tree.
Now you can see what we go back in the main procedure and display the contents of the first tree. If interested, you can skip the creation of a new node and just update the nodes in the left input tree (replace m with t1 in 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 2759 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
Twitter: @john_canessa