Good evening. Hope you are doing well. As I mentioned in the prior post, yesterday I attended a webinar and was able to watch a software engineer in a mock interview solve two programming problems. This post deals with the second problem. My approach is different to the one used by the developer on the webinar. If you follow this blog, you should have looked at the code that I have written to handle processing binary trees. In most examples involving a binary tree LeetCode uses the TreeNode class for the nodes. The problem in the webinar did not make any reference to LeetCode, but I like to solve problems in sites that offer extensive tests. That way one can be relatively sure that the solution is bug free.
The problem that I watched being solved presented a binary tree with values on upper case characters. LeetCode used nodes with integer values. That should not affect the approach or the solution.
As you might be aware, I like to solve the problems on my machine. In this post I will use Java on a Windows 10 computer and the VSCode IDE. To be honest with you, the IDE is similar to Visual Studio but it has some small issues that I tend to run into when I start a project. The first few times I need an automatic reference to a class the IDE does not seem to provide the proper suggestions. After a few lines of codes that have required some imports, things appear to work fine. Not sure why the IDE behaves like that. If you have any suggestions on what I could do to address this minor issue, I would like to hear from you.
The problem that we will solve is LeetCode 102 Binary Tree Level Order Traversal. After I felt all was well with the code, I copied and pasted the contents of the function / method we have to implement into the LeetCode site. I then execute the code. If all is well I submit it and see if it is accepted.
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
The problem statement is quite simple. We are given a binary tree and are required to return a list holding a set of lists, one per level containing the values for the nodes in a left to right order.
/**
* 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 List<List<Integer>> levelOrder(TreeNode root) {
}
}
The TreeNode class is provided by LeetCode. I have to implement it since I am developing the code on my computer. We are also provided with the signature for the function / method we need to implement. In my case I will have to collect the data for the binary tree and populate the binary tree. At that point I should be able to call the function / method in question and display the results.
3,9,20,null,null,15,7 main <<< strArr: [3, 9, 20, null, null, 15, 7] main <<< arr: [3, 9, 20, null, null, 15, 7] main <<< root: [[3], [9, 20], [15, 7]] main <<< ans: [[3], [9, 20], [15, 7]] [3], [9,20], [15,7]
LeetCode provides one example. Our test code needs to read the input line and generate a string array with the node values. With that done we seem to populate an Integer[] with the values. If we would have used a int[] array we could not have used null for values.
The next line is the display of the binary tree in level order. This produces the same results that we have not generated yet but will be asked to generate and display as part of the solution. The last line labeled ‘ans:’ displays the same data but this time is the code for this solution. I just felt to generate a different solution. If you see the code that implements some of the TreeNode class methods, as usual you can find them in my GitHub repository (https://github.com/JohnCanessa/BinaryTreeLevelOrderTraversal).
/**
* Test scaffolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read and populate String array ****
String[] strArr = br.readLine().trim().split(",");
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< strArr: " + Arrays.toString(strArr));
// **** create and populate Integer array ****
Integer[] arr = new Integer[strArr.length];
for (int i = 0; i < arr.length; i++) {
if (strArr[i].equals("null"))
arr[i] = null;
else
arr[i] = Integer.parseInt(strArr[i]);
}
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** create the root for the binary tree ****
TreeNode root = new TreeNode();
// **** populate the binary tree ****
root = root.populate(arr);
// ???? ????
System.out.println("main <<< root: " + root.levelOrderTraversal(root));
// **** generate and display the binary tree in level order ****
System.out.println("main <<< ans: " + levelOrder(root));
}
This code implements the test scaffolding I had to write to collect the input, generate the binary tree, pass it to the method of interest and display the results. The main() function / method IS NOT PART OF THE SOLUTION.
We open a buffered reader, read the input line, generate a String[] array with the values for the nodes and close the buffered reader. With that String[] we create and populate an Integer[] which will be used to load the binary tree in level order. This is the reverse operation we are asked to implement as a solution. We display the binary tree in level order to make sure all is well. Finally we call our solution and display the results.
The results match and the code was accepted by LeetCode.
/**
* Given a binary tree, return the level order traversal of its nodes' values.
* (ie, from left to right, level by level).
*
* Runtime: 1 ms, faster than 55.20% of Java online submissions.
* Memory Usage: 39.1 MB, less than 81.39% of Java online submissions.
*/
static List<List<Integer>> levelOrder(TreeNode root) {
// **** sanity checks ****
if (root == null) {
return new ArrayList<List<Integer>>();
}
// **** initialization****
List<List<Integer>> lst = new ArrayList<List<Integer>>();
LinkedList<TreeNode> primaryQ = new LinkedList<>();
LinkedList<TreeNode> secondaryQ = new LinkedList<>();
ArrayList<Integer> al = new ArrayList<Integer>();
lst.add(al);
// **** prime the primary queue ****
primaryQ.offer(root);
// **** loop while the primary queue is not empty O(n) ****
while (!primaryQ.isEmpty()) {
// **** remove head node ****
TreeNode node = primaryQ.remove();
// **** add node value to the array list ****
al.add(node.val);
// **** offer left child ****
if (node.left != null)
secondaryQ.offer(node.left);
// **** offer right child ****
if (node.right != null)
secondaryQ.offer(node.right);
// **** swap queues (if needed) ****
if (primaryQ.isEmpty() && !secondaryQ.isEmpty()) {
// **** swap queues ****
primaryQ = secondaryQ;
// **** create new queue ****
secondaryQ = new LinkedList<>();
// **** create new array list ****
al = new ArrayList<Integer>();
lst.add(al);
}
}
// **** return list of list ****
return lst;
}
We start by performing some sanity checks.
We initialize the array list in which we will return our answer. We will use two queues to perform the binary tree level order traversal. Finally we initialize the array list used to store the value of the first level in the tree which corresponds to the root node.
We then prime the primary queue with the root node and enter a loop that will process all the nodes in the binary tree.
We take the first node from the primary queue. We add the node value to the array list for the current level. We then offer the child nodes to the secondary queue.
If the primary queue is empty (will be in the first pass) we swap the primary with the secondary queue. We create a new secondary queue and a new array list to hold the values for the next level in the binary tree.
After we are done processing all the nodes in the binary tree we return the list of lists to the caller.
Hope you enjoyed solving this problem as much as I did. 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 help out 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 e-mail message. 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 5,509 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.
Regards;
John
john.canessa@gmail.com