Hi gals and guys! It is Friday afternoon and we have a long weekend ahead. Hope you enjoy Independence Day in the USA. The weather in my neck of the woods will be in the lower 90’s F thru Monday. On Tuesday the temperature will drop a few degrees and it seems we might receive some precipitation in the Twin Cities of Minneapolis and St. Paul.
On a separate note, it appears that the UPS attached to one of my computers is starting to fail. One of the internal batteries does not seem to be charging as it should. I guess it is time to replace the unit. I believe I purchased the UPS about 10 years ago. OK, I just ordered a replacement on Amazon. The UPS should arrive on Friday this week.
My wife is calling me to go out grocery shopping. I will finish this post tomorrow morning…
… I am back. It is Saturday morning. After breakfast, my wife and I went out for a walk. The high temperature for the day will be in the low 90s F. Glad we are done walking. In a couple hours or so we will be heading out to get some groceries. After that we need to do some travel planning. It is already July 03. Shortly the temperature will drop and fall will be here.
In this post we will take a look at LeetCode 366 Find Leaves of Binary Tree which is part of the daily July coding challenge. During the next two months including July, I will try to solve as many problems as I can. Due to other commitments I will not be ready to give my full daily attention until the month of September 2021.
Given the root of a binary tree, collect a tree's nodes as if you were doing this: o Collect all the leaf nodes. o Remove all the leaf nodes. o Repeat until the tree is empty.
The requirements are somewhat misleading. The first step is to collect leaf nodes. The second step states that we should remove such nodes from the binary tree. We then need to repeat the two previous steps until the binary tree is empty.
/**
* 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>> findLeaves(TreeNode root) {
}
}
We must use the TreeNode class provided by LeetCode. This class is typically used in binary tree problems.
The signature for the function of interest receives as argument the root of the binary tree and returns a List<List<Integer>> representing the leave nodes that have been deleted on each pass. It makes sense.
I will not be using the on-line IDE provided by LeetCode. I will be using the Java programming language and the VSCode IDE on a Windows computer. The reason is to have both the test code and solution in one package that I can run locally without having access to the Internet. Because of this we will generate some test code which IS NOT PART OF THE SOLUTION.
main <<< strArr.length: 1 main <<< strArr: [] main <<< arr: [null] main <<< bst.inOrder: main <<< bst.levelOrderTraversal: [] main <<< findLeaves: [] 1 main <<< strArr.length: 1 main <<< strArr: [1] main <<< arr: [1] main <<< bst.inOrder: 1 main <<< bst.levelOrderTraversal: [[1]] findLeaves <<< leaves: [1] main <<< findLeaves: [[1]] 1,2 main <<< strArr.length: 2 main <<< strArr: [1, 2] main <<< arr: [1, 2] main <<< bst.inOrder: 2 1 main <<< bst.levelOrderTraversal: [[1], [2]] findLeaves <<< val: 1 findLeaves <<< val: 2 findLeaves <<< leaves: [2] findLeaves <<< val: 1 findLeaves <<< leaves: [1] main <<< findLeaves: [[2], [1]] 1,2,3 main <<< strArr.length: 3 main <<< strArr: [1, 2, 3] main <<< arr: [1, 2, 3] main <<< bst.inOrder: 2 1 3 main <<< bst.levelOrderTraversal: [[1], [2, 3]] findLeaves <<< val: 1 findLeaves <<< val: 2 findLeaves <<< val: 3 findLeaves <<< leaves: [2, 3] findLeaves <<< val: 1 findLeaves <<< leaves: [1] main <<< findLeaves: [[2, 3], [1]] 1,2,3,4,5 main <<< strArr.length: 5 main <<< strArr: [1, 2, 3, 4, 5] main <<< arr: [1, 2, 3, 4, 5] main <<< bst.inOrder: 4 2 5 1 3 main <<< bst.levelOrderTraversal: [[1], [2, 3], [4, 5]] findLeaves <<< val: 1 findLeaves <<< val: 2 findLeaves <<< val: 4 findLeaves <<< val: 5 findLeaves <<< val: 3 findLeaves <<< leaves: [4, 5, 3] findLeaves <<< val: 1 findLeaves <<< val: 2 findLeaves <<< leaves: [2] findLeaves <<< val: 1 findLeaves <<< leaves: [1] main <<< findLeaves: [[4, 5, 3], [2], [1]] 1,2,3,null,4,null,null,5,null,null,null main <<< strArr.length: 11 main <<< strArr: [1, 2, 3, null, 4, null, null, 5, null, null, null] main <<< arr: [1, 2, 3, null, 4, null, null, 5, null, null, null] main <<< bst.inOrder: 2 5 4 1 3 main <<< bst.levelOrderTraversal: [[1], [2, 3], [4], [5]] findLeaves <<< val: 1 findLeaves <<< val: 2 findLeaves <<< val: 4 findLeaves <<< val: 5 findLeaves <<< val: 3 findLeaves <<< leaves: [5, 3] findLeaves <<< val: 1 findLeaves <<< val: 2 findLeaves <<< val: 4 findLeaves <<< leaves: [4] findLeaves <<< val: 1 findLeaves <<< val: 2 findLeaves <<< leaves: [2] findLeaves <<< val: 1 findLeaves <<< leaves: [1] main <<< findLeaves: [[5, 3], [4], [2], [1]] 1,2,3,4,5,6,7 main <<< strArr.length: 7 main <<< strArr: [1, 2, 3, 4, 5, 6, 7] main <<< arr: [1, 2, 3, 4, 5, 6, 7] main <<< bst.inOrder: 4 2 5 1 6 3 7 main <<< bst.levelOrderTraversal: [[1], [2, 3], [4, 5, 6, 7]] findLeaves <<< val: 1 findLeaves <<< val: 2 findLeaves <<< val: 4 findLeaves <<< val: 5 findLeaves <<< val: 3 findLeaves <<< val: 6 findLeaves <<< val: 7 findLeaves <<< leaves: [4, 5, 6, 7] findLeaves <<< val: 1 findLeaves <<< val: 2 findLeaves <<< val: 3 findLeaves <<< leaves: [2, 3] findLeaves <<< val: 1 findLeaves <<< leaves: [1] main <<< findLeaves: [[4, 5, 6, 7], [2, 3], [1]] 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 main <<< strArr.length: 15 main <<< strArr: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] main <<< arr: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] main <<< bst.inOrder: 8 4 9 2 10 5 11 1 12 6 13 3 14 7 15 main <<< bst.levelOrderTraversal: [[1], [2, 3], [4, 5, 6, 7], [8, 9, 10, 11, 12, 13, 14, 15]] findLeaves <<< val: 1 findLeaves <<< val: 2 findLeaves <<< val: 4 findLeaves <<< val: 8 findLeaves <<< val: 9 findLeaves <<< val: 5 findLeaves <<< val: 10 findLeaves <<< val: 11 findLeaves <<< val: 3 findLeaves <<< val: 6 findLeaves <<< val: 12 findLeaves <<< val: 13 findLeaves <<< val: 7 findLeaves <<< val: 14 findLeaves <<< val: 15 findLeaves <<< leaves: [8, 9, 10, 11, 12, 13, 14, 15] findLeaves <<< val: 1 findLeaves <<< val: 2 findLeaves <<< val: 4 findLeaves <<< val: 5 findLeaves <<< val: 3 findLeaves <<< val: 6 findLeaves <<< val: 7 findLeaves <<< leaves: [4, 5, 6, 7] findLeaves <<< val: 1 findLeaves <<< val: 2 findLeaves <<< val: 3 findLeaves <<< leaves: [2, 3] findLeaves <<< val: 1 findLeaves <<< leaves: [1] main <<< findLeaves: [[8, 9, 10, 11, 12, 13, 14, 15], [4, 5, 6, 7], [2, 3], [1]] -64,12,18,-4,-53,null,76,null,-51,null,null,-93,3,null,-31,47,null,3,53,-81,33,4,null,-51,-44,-60,11,null,null,null,null,78,null,-35,-64,26,-81,-31,27,60,74,null,null,8,-38,47,12,-24,null,-59,-49,-11,-51,67,null,null,null,null,null,null,null,-67,null,-37,-19,10,-55,72,null,null,null,-70,17,-4,null,null,null,null,null,null,null,3,80,44,-88,-91,null,48,-90,-30,null,null,90,-34,37,null,null,73,-38,-31,-85,-31,-96,null,null,-18,67,34,72,null,-17,-77,null,56,-65,-88,-53,null,null,null,-33,86,null,81,-42,null,null,98,-40,70,-26,24,null,null,null,null,92,72,-27,null,null,null,null,null,null,-67,null,null,null,null,null,null,null,-54,-66,-36,null,-72,null,null,43,null,null,null,-92,-1,-98,null,null,null,null,null,null,null,39,-84,null,null,null,null,null,null,null,null,null,null,null,null,null,-93,null,null,null,98 main <<< strArr.length: 194 main <<< strArr: [-64, 12, 18, -4, -53, null, 76, null, -51, null, null, -93, 3, null, -31, 47, null, 3, 53, -81, 33, 4, null, -51, -44, -60, 11, null, null, null, null, 78, null, -35, -64, 26, -81, -31, 27, 60, 74, null, null, 8, -38, 47, 12, -24, null, -59, -49, -11, -51, 67, null, null, null, null, null, null, null, -67, null, -37, -19, 10, -55, 72, null, null, null, -70, 17, -4, null, null, null, null, null, null, null, 3, 80, 44, -88, -91, null, 48, -90, -30, null, null, 90, -34, 37, null, null, 73, -38, -31, -85, -31, -96, null, null, -18, 67, 34, 72, null, -17, -77, null, 56, -65, -88, -53, null, null, null, -33, 86, null, 81, -42, null, null, 98, -40, 70, -26, 24, null, null, null, null, 92, 72, -27, null, null, null, null, null, null, -67, null, null, null, null, null, null, null, -54, -66, -36, null, -72, null, null, 43, null, null, null, -92, -1, -98, null, null, null, null, null, null, null, 39, -84, null, null, null, null, null, null, null, null, null, null, null, null, null, -93, null, null, null, 98] main <<< arr: [-64, 12, 18, -4, -53, null, 76, null, -51, null, null, -93, 3, null, -31, 47, null, 3, 53, -81, 33, 4, null, -51, -44, -60, 11, null, null, null, null, 78, null, -35, -64, 26, -81, -31, 27, 60, 74, null, null, 8, -38, 47, 12, -24, null, -59, -49, -11, -51, 67, null, null, null, null, null, null, null, -67, null, -37, -19, 10, -55, 72, null, null, null, -70, 17, -4, null, null, null, null, null, null, null, 3, 80, 44, -88, -91, null, 48, -90, -30, null, null, 90, -34, 37, null, null, 73, -38, -31, -85, -31, -96, null, null, -18, 67, 34, 72, null, -17, -77, null, 56, -65, -88, -53, null, null, null, -33, 86, null, 81, -42, null, null, 98, -40, 70, -26, 24, null, null, null, null, 92, 72, -27, null, null, null, null, null, null, -67, null, null, null, null, null, null, null, -54, -66, -36, null, -72, null, null, 43, null, null, null, -92, -1, -98, null, null, null, null, null, null, null, 39, -84, null, null, null, null, null, null, null, null, null, null, null, null, null, -93, null, null, null, 98] main <<< bst.inOrder: -4 -51 -81 -31 33 12 -53 -64 18 78 4 47 -93 76 8 -35 -67 -38 -51 73 -33 3 -54 86 -66 -38 -37 -36 81 -31 -72 -42 80 -85 47 98 43 -31 -40 44 70 -92 -96 -93 -1 -26 -98 -19 -88 -64 24 -18 -91 67 10 12 34 92 48 72 72 -27 98 39 -55 -90 -17 3 -77 -30 72 -24 26 -44 -59 -81 -70 56 90 -84 -67 -65 -49 -88 -34 -53 17 37 3 -4 -11 -31 -51 -60 67 27 53 60 11 74 main <<< bst.levelOrderTraversal: [[-64], [12, 18], [-4, -53, 76], [-51, -93, 3], [-31, 47, 3, 53], [-81, 33, 4, -51, -44, -60, 11], [78, -35, -64, 26, -81, -31, 27, 60, 74], [8, -38, 47, 12, -24, -59, -49, -11, -51, 67], [-67, -37, -19, 10, -55, 72, -70, 17, -4], [3, 80, 44, -88, -91, 48, -90, -30, 90, -34, 37], [73, -38, -31, -85, -31, -96, -18, 67, 34, 72, -17, -77, 56, -65, -88, -53], [-33, 86, 81, -42, 98, -40, 70, -26, 24, 92, 72, -27, -67], [-54, -66, -36, -72, 43, -92, -1, -98, 39, -84], [-93, 98]] main <<< findLeaves: [[-81, 33, -53, 78, 8, -67, -33, -54, -66, -36, -72, -85, 43, -40, -92, -93, -98, -88, 24, 67, 92, 72, 98, -17, -77, -59, 56, -84, -88, -53, 37, -4, -51, 67, 60, 74], [-31, 4, -38, 73, 86, 81, -42, 98, 70, -1, -18, 34, 39, -90, -30, -67, -34, -11, 27, 11], [-51, 47, -35, -38, -31, -31, -26, -91, -27, 72, -65, 17, -31], [-4, -93, 3, 80, -96, 10, 72, -24, 90, -60], [12, -37, 44, 48, 26, -70, 53], [-19, -55, -49], [47, 12, -81], [-64, -44], [-51], [3], [3], [76], [18], [-64]]
There is a single input line for each test case. It represents the nodes in a binary tree.
Our test code reads the input line and seems to put the values in a string array. The length of the array is displayed followed by the actual contents of the array. The values seem to match.
Apparently our test code builds a binary tree and a BST in-order traversal is performed. The results are displayed.
A DFT is then performed and the results are displayed. This test case is the one used by LeetCode. You can see a diagram of the binary tree on the LeetCode web site.
Apparently our solution implements some type of DFS traversal to select the leave nodes. It seems that we can prune the sample binary tree in three passes.
When all is set and done the results are displayed.
Initially I went with an approach that removed the nodes and was based on DFS traversal. It passes 66 of 67 test cases. It failed the last test case. Not checking other test cases, my approach was dependent on not having nodes with the same value. Sadly, at least the last test case had enough duplicate values to cause my approach to fail.
/**
* Test scaffold
* !!! NOT PART OF SOLUTION !!!
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** initialization ****
// HashSet<Integer> hs = new HashSet<Integer>();
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** create String[] with values for the BST ****
String[] strArr = br.readLine().trim().split(",");
// **** close buffere reader ****
br.close();
// ???? ????
System.out.println("main <<< strArr.length: " + strArr.length);
System.out.println("main <<< strArr: " + Arrays.toString(strArr));
// **** generate an Integer[] to build the binary tree ****
Integer[] arr = new Integer[strArr.length];
for (int i = 0; i < strArr.length; i++) {
if (strArr[i].equals("null") || strArr[i].isEmpty())
arr[i] = null;
else
arr[i] = Integer.parseInt(strArr[i]);
}
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// // **** check and count duplicate values ****
// int duplicateValues = 0;
// for (int i = 0; i < arr.length; i++) {
// // **** skip null values ****
// if (arr[i] == null)
// continue;
// // **** ****
// if (hs.contains(arr[i]) == true)
// System.out.println("main <<< arr[" + i + "]: " + arr[i]
// + " duplicateValues: " + ++duplicateValues);
// else
// hs.add(arr[i]);
// }
// **** create and populate the binary tree ****
BST bst = new BST();
bst.root = bst.populate(arr);
// ???? ????
System.out.println("main <<< bst.inOrder: " + bst.inOrder(bst.root));
// ???? ????
System.out.print("main <<< bst.levelOrderTraversal: ");
System.out.println(bst.levelOrderTraversal(bst.root).toString());
// **** compute and display result ****
// System.out.println("main <<< findLeaves0: " + findLeaves0(bst.root));
// **** compute and display result ****
System.out.println("main <<< findLeaves: " + findLeaves(bst.root));
}
The test code seems to match the description used to describe the test cases.
Note that at some point I added a hash map to count duplicate values. This was to verify that my original approach was flawed and only worked when the binary tree had unique values.
I apologize but the code for my first pass was lost. As soon as I determined that it was not going to work I moved into a second pass without saving the first attempt.
The function of interest is called at the end of the test code. The results are displayed.
The functions to create and display binary trees are included in separate files in the GitHub repository for this post. They are NOT PART OF THE SOLUTION.
There is a slower second pass that we will not cover at this time. If interested you can find the two associated functions in the GitHub repository associated with this post.
/**
* Given the root of a binary tree, collect a tree's nodes as if you were doing this:
*
* o Collect all the leaf nodes.
* o Remove all the leaf nodes.
* o Repeat until the tree is empty.
*
* Runtime: O(n) Space: O(n)
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 37.3 MB, less than 79.87% of Java online submissions.
*/
static List<List<Integer>> findLeaves(TreeNode root) {
// **** initialization ****
List<List<Integer>> lol = new ArrayList<>();
// **** loop until we have no more nodes to process ****
while (root != null) {
// **** new list of leaves ****
List<Integer> leaves = new ArrayList<>();
// **** find leaf nodes on this pass ****
root = findLeaves(root, leaves);
// ???? ????
// System.out.println("findLeaves <<< leaves: " + leaves.toString());
// **** add list of leaf nodes to the list ****
lol.add(leaves);
}
// **** return list of lists ****
return lol;
}
This is the function of interest.
We start by declaring an array list that will hold the lists of leaf node values.
We then perform a sanity check.
A recursive call is then invoked. In the second parameter we pass the array list.
After the recursion completes, we display the contents of the array list.
In the dfs function we are about to see, we are going to use an approach similar to the one we implemented in the Maximum Depth of a Binary Tree post. This might be a good time to take a quick look at the function of interest in that post. I will wait for you to return …
… OK, now that you are back we can proceed. This is the entry point for the function of interest.
We start by allocating an array list which will be used to store the end notes on each pass.
We then enter a loop that will end when the root of the tree becomes null.
In the loop we declare an array list that will be used to store the end leaf nodes of the current pass.
We then call the recursive function that will populate the leaves list and will update the root node when done.
The leaves are added to the `lol` list after each pass / loop.
/**
* Recursive call.
*/
static TreeNode findLeaves(TreeNode root, List<Integer> leaves) {
// **** base condition(s) ****
if (root == null) return root;
// ???? ????
// System.out.println("findLeaves <<< val: " + root.val);
// **** found leaf node ****
if (root.left == null && root.right == null) {
// **** add it to list ****
leaves.add(root.val);
// **** ****
return null;
}
// **** recursion on left and right sub-trees ****
root.left = findLeaves(root.left, leaves);
root.right = findLeaves(root.right, leaves);
// **** return root ****
return root;
}
Let’s now get into the recursive call.
We have two base cases. The first is encountered when the root is null. This signals that we have processed and added to the leaves list the root of the binary tree.
The second case is when we encounter a leaf node that is not the root. This code takes care of all other leaf nodes. We add the value to the leaves list and return null indicating there are no more sub-trees to explore on this branch.
We then perform the recursive calls on the left and right sub trees.
When all is said and done we return the root of the binary tree.
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, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John