Labor Day weekend 2020 is here. The temperatures in the Twin Cities of Minneapolis and St. Paul are getting lower. Given COVID-19, the Minnesota State Fair has been postponed this year. My wife and I are not fair goers. We have been there twice. Our oldest son, who lives in this area, tends to go at least once a year.
Yesterday my wife and I grilled a whole chicken and some steak. There were chicken leftovers for the week. Not sure what we will grill for lunch today. Today the high temperature will be in the lower 80’s. It should be a great day to grill.
In this post I will cover my experience attempting to solve LeetCode problem 894. All Possible Full Binary Trees. If interested take a look at the requirements.
Before we go too far, let’s make sure we understand the concept of full binary trees. The idea is simple but it is always good to experiment with some examples to make sure we understand the concept. If you take a BT (binary tree for short) with a single node, it would qualify because the BT only node has two null children.
If you go to two nodes, based on the definition, the root tree will have one child (on the left or the right). So it would not qualify.
When we get to three nodes, the root would have two children, and each of the two nodes in the second level, would have no children. This tree would qualify.
A BT with four nodes would have to be discarded, but a tree with five nodes would qualify. As always, before proceeding, let’s make sure we are able to draw the two possible solutions.
A full binary tree is a binary tree where each node has exactly 0 or 2 children. Return a list of all possible full binary trees with N nodes. Each element of the answer is the root node of one possible tree. Each node of each tree in the answer must have node.val = 0. You may return the final list of trees in any order.
LeetCode provides a good description of the problem. Make sure we read it in detail.
/**
* 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<TreeNode> allPossibleFBT(int N) {
}
}
LeetCode provides the definition of the TreeNode class which is used to build the binary trees. We are charged with developing the code for the allPossibleFBT() function.
The test scaffolding that we will build is not part of the solution. I built one 
because I prefer to develop software on my computers using the tools I like. Of course, you are welcome to skip the section that deals with the test scaffolding, and just hone on the two approaches the implement the solution. The first does not use memoization but the second does. Memoization is the concept of storing or caching partial results that may be reused once or multiple times in the scope of a solution.
For this post, I used Java on a Windows 10 machine and the Visual Studio Code IDE to solve the problem. The IDE should make no different as long as it supports Java. A Linux or Windows computer should be fine.
1 main <<< N: 1 main <<< lst [[0]] main <<< lst.size: 1 allPossibleFBTMemo <<< cached N: 1 main <<< lst [[0]] main <<< lst.size: 1 main <<< String max length: 2147483647 2 main <<< N: 2 main <<< lst [] main <<< lst.size: 0 main <<< lst [] main <<< lst.size: 0 main <<< String max length: 2147483647 3 main <<< N: 3 main <<< lst [[0,0,0]] main <<< lst.size: 1 allPossibleFBTMemo <<< cached N: 1 allPossibleFBTMemo <<< cache hit N: 1 allPossibleFBTMemo <<< cached N: 3 main <<< lst [[0,0,0]] main <<< lst.size: 1 main <<< String max length: 2147483647 5 main <<< N: 5 main <<< lst [[0,0,0,null,null,0,0],[0,0,0,0,0,null,null]] main <<< lst.size: 2 allPossibleFBTMemo <<< cached N: 1 allPossibleFBTMemo <<< cache hit N: 1 allPossibleFBTMemo <<< cache hit N: 1 allPossibleFBTMemo <<< cached N: 3 allPossibleFBTMemo <<< cache hit N: 3 allPossibleFBTMemo <<< cache hit N: 1 allPossibleFBTMemo <<< cached N: 5 main <<< lst [[0,0,0,null,null,0,0],[0,0,0,0,0,null,null]] main <<< lst.size: 2 main <<< String max length: 2147483647 7 main <<< N: 7 main <<< lst [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0,null,null],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0,null,null]] main <<< lst.size: 5 allPossibleFBTMemo <<< cached N: 1 allPossibleFBTMemo <<< cache hit N: 1 allPossibleFBTMemo <<< cache hit N: 1 allPossibleFBTMemo <<< cache hit N: 1 allPossibleFBTMemo <<< cached N: 3 allPossibleFBTMemo <<< cache hit N: 3 allPossibleFBTMemo <<< cache hit N: 1 allPossibleFBTMemo <<< cached N: 5 allPossibleFBTMemo <<< cache hit N: 3 allPossibleFBTMemo <<< cache hit N: 3 allPossibleFBTMemo <<< cache hit N: 5 allPossibleFBTMemo <<< cache hit N: 1 allPossibleFBTMemo <<< cached N: 7 main <<< lst [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0,null,null],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0,null,null]] main <<< lst.size: 5 main <<< String max length: 2147483647
The test scenarios appear to provide an integer which we need to read into the test scaffolding. The value is then displayed to verify we were able to read it. It seems that the software displays a list of trees with their size. So far that takes care of the first four lines in each example.
The next set of output lines seem to display information related to the memoization mechanism we use to cache data that may be reused. The size of the cache is displayed followed by a line holding the results. The size of the list holding the results is displayed. The value of the maximum Integer is also displayed. This information is not required by the problem. I will explain more as we proceed.
We have in total five examples. We can deduct that only BTs with odd number of nodes would produce viable solutions.
/**
* 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;
}
// **** display the value of the TreeNode object (not needed for solution) ****
@Override
public String toString() {
return "" + this.val;
}
}
I took the commented out definition for the TreeNode class provided by LeetCode and inserted into my code. I also added the toString() method in order to display the value of the nodes. You do not need to copy or make this change if you are using the test scaffolding provided by LeetCode.
/**
* Test scaffolding.
*/
public static void main(String[] args) throws Exception{
// **** ****
List<TreeNode> lst = null;
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read N ****
int N = sc.nextInt();
// **** close scanner ****
sc.close();
// ???? ????
System.out.println("main <<< N: " + N);
// **** check number of nodes in the BT ****
if ((N < 1) || N > 20) {
throw new Exception("EXCEPTION - N > 20");
}
// **** generate list of full binary trees ****
lst = allPossibleFBT(N);
// **** display the binary tree list ****
System.out.println("main <<< lst " + displayBTList(lst));
// **** display the length of the list ****
System.out.println("main <<< lst.size: " + lst.size());
// **** generate list of full binary trees (with memoization) ****
lst = allPossibleFBTMemo(N);
// **** display the binary tree list ****
System.out.println("main <<< lst " + displayBTList(lst));
// **** display the length of the list ****
System.out.println("main <<< lst.size: " + lst.size());
// ???? display the cache ????
// System.out.println("main <<< cache: " + cache.toString());
// ???? ????
System.out.println("main <<< String max length: " + Integer.MAX_VALUE);
}
The test scaffolding is quite simple. We open a scanner, read in the number of nodes, close the scanner and display the value. I added a check to verify that the user (in this case me) will not enter integers larger than 20.
The allPossibleFBT() function is then called. The list of all possible BTs is returned. We display the list to see if we got the expected set.
We then call the allPossibleFBTMemo() function. This function will use memoization (caching) to store partial BTs and be able to get them if and when needed. I left a couple messages that show what is being cached and when BTs are recalled. Once again the BTs are displayed. Both lists should hold the same BTs.
Towards the bottom of the test scaffolding we may display the cache used for memoization (commented at this point) and the number of full BTs returned by the functions.
The reason that the largest Integer is displayed is that as you run the test scaffolding and specify larger number of nodes, the number of BTs grows and the length of the returned strings grows accordingly. Depending on the amount of memory in your computer and how the VM is configured, the program may crash when generating a single string for the results. We could have returned and possibly display individual strings per BT, but I did not. I assume that the same is done in the LeetCode test scaffolding due to the limits for N in the requirements specification.
/**
* Return a string with the list of trees.
*/
static String displayBTList(List<TreeNode> lst) throws Exception {
// **** ****
StringBuilder sb = new StringBuilder();
try {
// **** generate the string for all BTs ****
sb.append("[");
for (int i = 0; i < lst.size(); i++) {
bfsTraversal(lst.get(i), sb);
if (i < lst.size() - 1)
sb.append(",");
}
sb.append("]");
} catch (Exception e) {
System.out.println("displayBTList <<<< EXCEPTION ==>" + e.getMessage() + "<==");
}
// **** return the string ****
return sb.toString();
}
The displayBTList() function (perhaps a better name is needed) returns a string representing all the trees with all the nodes in the specified list of trees. I first worked on displaying the nodes in order to avoid huge strings, but then I switched to return a string given the requirement constrains for N.
The idea is to use a StringBuilder for performance. We append to it the representation of all the BTs in the specified set. This function, given the specified requirements, does not need to throw an exception. I just left it in case you might be interested in experimenting with String size limits. That is outside the scope of this problem as well as this function which is only used by my test scaffolding.
At the core of the function we implement a loop that traverses a BT and appends BT representations to the StringBuilder which is converted to a string to be returned.
/*
* This method implements a breadth-first search traversal of a binary tree.
* This method is iterative.
* It displays all nodes at each level on a separate line.
*/
static void bfsTraversal(TreeNode root, StringBuilder sb) {
// **** end of tree flag ****
boolean endOfTree = false;
// **** define the current and next queues ****
List<TreeNode> currentQ = new LinkedList<TreeNode>();
List<TreeNode> nextQ = new LinkedList<TreeNode>();
// **** add the root node to the current queue ****
currentQ.add(root);
// **** ****
sb.append("[");
// **** loop while the current queue has entries ****
while (!currentQ.isEmpty()) {
// **** remove the next node from the current queue ****
TreeNode n = currentQ.remove(0);
// **** display the node value ****
if (n != null)
sb.append(n.toString());
else
sb.append("null");
// **** add left and right children to the next queue ****
if (n != null) {
if (n.left != null)
nextQ.add(n.left);
else
nextQ.add(null);
if (n.right != null)
nextQ.add(n.right);
else
nextQ.add(null);
}
// **** check if the current queue is empty (reached end of level) ****
if (currentQ.isEmpty()) {
// **** check if we have all null nodes in the next queue ****
boolean allNulls = true;
for (TreeNode t : nextQ) {
if (t != null) {
allNulls = false;
break;
}
}
// **** point the current to the next queue ****
currentQ = nextQ;
// **** clear the next queue ****
nextQ = new LinkedList<TreeNode>();
// **** clear the current queue (all null nodes) ****
if (allNulls)
currentQ = new LinkedList<TreeNode>();
// **** flag we are done with this tree ****
if (allNulls)
endOfTree = true;
}
// **** display ',' (node separator) ****
if (endOfTree)
sb.append("]");
else
sb.append(',');
}
}
The bfsTraversal() function traverses the specified BT and adds a representation to the specified StringBuilder. As the name states, we perform a Breath First Search (traversal in this case) of a specified tree. That allows us to process in order all the nodes at the same level in order left to right.
The approach is quite standard when performing breadth first traversals. We use two queues. We prime the current queue and we process the nodes converting and adding their children to the next queue. When done with the current level, we swap queues and repeat the process. If you are not comfortable with this method, I would suggest for you to spend some time getting to fully understand how this algorithm works.
There are a few things that I added to the base function so the output would match what LeetCode shows. Keep in mind that the use of this function is out of the scope of the problem. The function is only used by my test scaffolding. In addition, the output did not have to match the output by LeetCode. What is important is that the set of BTs is correct.
/**
* Return a list of all possible full binary trees with N nodes.
* Each element of the answer is the root node of one possible tree.
* 1 <= N <= 20
* Recursive function.
*/
static List<TreeNode> allPossibleFBT(int N) {
// **** list of compliant binary tree(s) ****
List<TreeNode> lst = new ArrayList<TreeNode>();
// **** if N is even (no possible answer) ****
if (N % 2 == 0)
return lst;
// **** tree with single node ****
if (N == 1) {
lst.add(new TreeNode(0));
return lst;
}
// **** only consider odd counts ****
for (int i = 1; i < N; i += 2) {
// **** left trees ****
for (TreeNode left : allPossibleFBT(i)) {
// **** right trees ****
for (TreeNode right : allPossibleFBT(N - i - 1)) {
//// **** create and populate root node ****
//TreeNode root = new TreeNode(0);
//root.left = left;
//root.right = right;
//// **** add tree to list ****
//lst.add(root);
// **** create and add node (tree) to the list ****
lst.add(new TreeNode(0, left, right));
}
}
}
// **** return list of trees ****
return lst;
}
The allPossibleFBT() function is the solution for the problem. If you copy and paste the contents into LeetCode and run it, it should be accepted.
We create a list which will hold all the full binary trees that we can generate for the specified number of nodes. As we have mentioned, N == 1 represents a BT with a single node which is acceptable. We also discussed that even numbers are not able to generate valid solutions, so we need to skip them. Basically our problem is to process N in the following set: { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 }.
The solution consists of three loops. The outer one specifies the valid values to iterate through. The second loop takes care of the left children for the current node while the third loop takes care of the children for the right tree.
Since the function is recursive, the different BTs are created one node at a time. As expected, most of the trees will have mirrored versions.
// **** for memoization (caching) ****
private static Map<Integer, List<TreeNode>> cache = new HashMap<Integer, List<TreeNode>>();
/**
* Return a list of all possible full binary trees with N nodes.
* Each element of the answer is the root node of one possible tree.
* 1 <= N <= 20
* Recursive function.
* Uses memoization (caching).
*/
static List<TreeNode> allPossibleFBTMemo(int N) {
// **** list of compliant binary tree(s) ****
List<TreeNode> lst = new ArrayList<TreeNode>();
// **** empty list ****
if (N % 2 == 0)
return lst;
// ***** check if in cache ****
if (cache.containsKey(N)) {
// ???? ????
System.out.println("allPossibleFBTMemo <<< cache hit N: " + N);
// **** cache this tree ****
return cache.get(N);
}
// **** tree with single node ****
if (N == 1) {
// **** add node to list ****
lst.add(new TreeNode(0));
// **** cache this tree ****
cache.put(N, lst);
// ???? ????
System.out.println("allPossibleFBTMemo <<< cached N: " + N);
// **** return this list ****
return lst;
}
// **** *****
for (int i = 0; i < N; i++) {
// **** go into left tree ****
List<TreeNode> left = allPossibleFBTMemo(i);
// **** go into right tree ****
List<TreeNode> right = allPossibleFBTMemo(N - i - 1);
// **** add node to the tree ****
for (TreeNode l : left) {
for (TreeNode r : right) {
lst.add(new TreeNode(0, l, r));
}
}
}
// **** cache this tree ****
cache.put(N, lst);
// ???? ????
System.out.println("allPossibleFBTMemo <<< cached N: " + N);
// **** return this list ****
return lst;
}
This function is equivalent to the last one, but we will use memoization. With that in mind, we will declare a hash map which we will call cache. The idea is to store valid BTs with different values so in case they repeat, we will not need to generate them, we will just look them up in O(1) time.
By looking at the code it is quite similar to the previous one.
Note that we check before we create BTs. If we create a new BT we cache it for future use.
After the checks of N similar to what we did in the previous function, we loop creating the left side full BT followed by the right side full BT. We add the nodes in the two inner loops in a similar fashion as we did in the previous function.
We then cache the full BT we just generated and return the list.
Let’s go back to the screen capture of the test scaffolding outputs. The example for N = 5, we see that we need to generate two full BTs. The first function returns the two BTs as expected. The second function shows that we use in recursive mode values 1, 3, and 5. At some point we cache full BT for N = 1 and later on, we recall it three times. We also cache the full BT for N = 3, and recall it once. The first time the full BT for N = 3 is generated for the first full BT and in a later pass that same tree is recalled from cache to build the mirror version in this specific solution.
The entire code for this project can be found in my GitHub repository.
In my next post I will cover an item that is used by most system designs. I am referring to a load balancing. I recall writing a paper about it several years ago. I will try to implement a basic one using Java. The one I worked on before was written in C/C++.
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 1786 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
Twitter: @john_canessa