Hope you enjoyed Thanksgiving Day 2020. My wife and I did even though it was just the two of use for late lunch. We prepared our usual menu with some minor twists. The menu was a young turkey (we usually cook a 20+ lbs bird) which came in at around 11 lbs. with potatoes casserole and meat stuffing (we not prepare the popular / traditional bread based kind). For desert we had monkey bread which we got from one of our neighbors. We had a little more than we should, so we decided to skip our after lunch espresso.
For the turkey, we added some spices, a little garlic clove, some butter and apple vinegar. We inserted a thermometer and cook it to 175F. We then took it out of the oven and let it rest. Typically the temperature rises north of 180F. Since the turkey weighted 11 lbs., the temperature only went up to 178F.
The potatoes casserole has frozen diced potatoes, sour cream, cream of 
mushrooms, and shredded Colby Jack cheese (we shred the cheese in a Ninja blender). We mixed all the ingredients and put it in aluminum disposable containers. Cover them with graham cracker crumbs and pieces of butter. That goes in 1 350F preheated oven for an hour. When done, we let them to cool down. Then we cover them with aluminum foil and in to the refrigerator.
The potatoes casserole was done Wednesday. On Thursday we add more butter and covered them back with the aluminum foil. We the put the potatoes casserole into a room temperature oven, set the temperature to 400F and let them reheat. When the oven temperature reaches 400F, we remove the aluminum foils and let them brown for another 10 minutes. Then we take them out of the oven and wait for them to cool down to a point we can serve them. When the potatoes casserole comes out of the oven it is liquid magma (very hot). DO NOT TRY EATING IT BECAUSE YOU WILL GET BURNED!!!
The stuffing is an old recipe used in different parts of South America. You start with ground beef (80/20) and possibly ground pork. Yesterday we just used 5 lbs. of ground beef. We put the meat in a pot with some olive oil, salt, pepper, garlic and red onions (we used three). Move it every five minutes until all the meat is brown. You do not want to consume raw beef / pork!!!
After the meat is brown we add two cups of crushed walnuts and two cups of raisins. The amount of nuts and raisins should be adjusted based on taste. This is a good time to add some spices. My wife likes some Italian seasoning, red paprika and nutmeg. You should add what you like.
We like to add some Pisco (https://en.wikipedia.org/wiki/Pisco) which is 
alcohol distilled from grapes. Make sure you keep the pot at a medium low temperature for at least 15 more minutes for the alcohol to evaporate.
When done we deliver half of what we made to our granddaughters. They typically join us for Thanksgiving, but this year due to COVID-19, we all decided that it would be safer if they stayed home with their mother and we 
did our own thing.
OK, now to the main subject of this post. The evening after I published Validate Binary Search Tree I ran into a Reddit post about the LeetCode problem that I had just solved. After generating a short answer I went to sleep. During the night I was thinking about making a post on the different approach. Today I had some time so here it is.
20,10,30 main <<< inOrder: 10 20 30 main <<< inOrderIterative: 10 20 30 <<< push root: 20 <<< push root: 10 <<< stack bottom -> [20, 10] <<< pop root: 10 <<< prev: 10 <<< stack bottom -> [20] <<< pop root: 20 <<< prev: 20 <<< push root: 30 <<< stack bottom -> [30] <<< pop root: 30 <<< prev: 30 main <<< isValidBST1: true main <<< isValidBST2: true main <<< isValidBST0: true main <<< isValidBST: true 20,21,30 main <<< inOrder: 21 20 30 main <<< inOrderIterative: 21 20 30 <<< push root: 20 <<< push root: 21 <<< stack bottom -> [20, 21] <<< pop root: 21 <<< prev: 21 <<< stack bottom -> [20] <<< pop root: 20 <<< root: 20 <= prev: 21 !!! main <<< isValidBST1: false main <<< isValidBST2: false main <<< isValidBST0: false 10,5,15,1,7,11,17,null,null,null,9,null,null,16,19 main <<< inOrder: 1 5 7 9 10 11 15 16 17 19 main <<< inOrderIterative: 1 5 7 9 10 11 15 16 17 19 <<< push root: 10 <<< push root: 5 <<< push root: 1 <<< stack bottom -> [10, 5, 1] <<< pop root: 1 <<< prev: 1 <<< stack bottom -> [10, 5] <<< pop root: 5 <<< prev: 5 <<< push root: 7 <<< stack bottom -> [10, 7] <<< pop root: 7 <<< prev: 7 <<< push root: 9 <<< stack bottom -> [10, 9] <<< pop root: 9 <<< prev: 9 <<< stack bottom -> [10] <<< pop root: 10 <<< prev: 10 <<< push root: 15 <<< push root: 11 <<< stack bottom -> [15, 11] <<< pop root: 11 <<< prev: 11 <<< stack bottom -> [15] <<< pop root: 15 <<< prev: 15 <<< push root: 17 <<< push root: 16 <<< stack bottom -> [17, 16] <<< pop root: 16 <<< prev: 16 <<< stack bottom -> [17] <<< pop root: 17 <<< prev: 17 <<< push root: 19 <<< stack bottom -> [19] <<< pop root: 19 <<< prev: 19 main <<< isValidBST1: true main <<< isValidBST2: true main <<< isValidBST0: true main <<< isValidBST: true 10,5,15,1,7,11,17,null,null,null,9,null,null,2,19 main <<< inOrder: 1 5 7 9 10 11 15 2 17 19 main <<< inOrderIterative: 1 5 7 9 10 11 15 2 17 19 <<< push root: 10 <<< push root: 5 <<< push root: 1 <<< stack bottom -> [10, 5, 1] <<< pop root: 1 <<< prev: 1 <<< stack bottom -> [10, 5] <<< pop root: 5 <<< prev: 5 <<< push root: 7 <<< stack bottom -> [10, 7] <<< pop root: 7 <<< prev: 7 <<< push root: 9 <<< stack bottom -> [10, 9] <<< pop root: 9 <<< prev: 9 <<< stack bottom -> [10] <<< pop root: 10 <<< prev: 10 <<< push root: 15 <<< push root: 11 <<< stack bottom -> [15, 11] <<< pop root: 11 <<< prev: 11 <<< stack bottom -> [15] <<< pop root: 15 <<< prev: 15 <<< push root: 17 <<< push root: 2 <<< stack bottom -> [17, 2] <<< pop root: 2 <<< root: 2 <= prev: 15 !!! main <<< isValidBST1: false main <<< isValidBST2: false main <<< isValidBST0: false main <<< isValidBST: false 3,1,5,0,2,4,6,null,null,null,3 main <<< inOrder: 0 1 2 3 3 4 5 6 main <<< inOrderIterative: 0 1 2 3 3 4 5 6 <<< push root: 3 <<< push root: 1 <<< push root: 0 <<< stack bottom -> [3, 1, 0] <<< pop root: 0 <<< prev: 0 <<< stack bottom -> [3, 1] <<< pop root: 1 <<< prev: 1 <<< push root: 2 <<< stack bottom -> [3, 2] <<< pop root: 2 <<< prev: 2 <<< push root: 3 <<< stack bottom -> [3, 3] <<< pop root: 3 <<< prev: 3 <<< stack bottom -> [3] <<< pop root: 3 <<< root: 3 <= prev: 3 !!! main <<< isValidBST1: false main <<< isValidBST2: false main <<< isValidBST0: false main <<< isValidBST: false 5,1,4,null,null,3,6 main <<< inOrder: 1 5 3 4 6 main <<< inOrderIterative: 1 5 3 4 6 <<< push root: 5 <<< push root: 1 <<< stack bottom -> [5, 1] <<< pop root: 1 <<< prev: 1 <<< stack bottom -> [5] <<< pop root: 5 <<< prev: 5 <<< push root: 4 <<< push root: 3 <<< stack bottom -> [4, 3] <<< pop root: 3 <<< root: 3 <= prev: 5 !!! main <<< isValidBST1: false main <<< isValidBST2: false main <<< isValidBST0: false main <<< isValidBST: false
It seems that our test scaffolding reads a line of integers representing the binary tree depth first traversal. With that data the test scaffolding displays the generated binary tree in order. This is done twice. The first one seems to be using a recursive method, while the second one seems to use an iterative approach. Of course, both approaches, if correct, should display the values in ascending order and without duplicates. Any diversions should be attributed to the fact that the data does not qualify for a BST, which happens to be the topic for the problem.
It seems we process the data using four different approaches. Of interest in this post is the code for the isValidBST1() method. Note that the entire code has been posted to my GitHub repository associated with this post.
The method in question displays additional information which we will discuss shortly. If you wish to run the code in LeetCode, you must remove or comment out the debugging comments.
The four approaches seem to agree on the respective answers. That is reassuring. In addition I have submitted all four versions and they all were accepted by LeetCode.
I wish to note that most (never generalize) recursive algorithms may be implemented using an iterative approach. Recursive algorithms seem to use less code and run faster but make use of the execution stack. That tends to slow them up.
As we mentioned, the test scaffolding displays the binary tree twice, once using a recursive approach and the second an iterative one.
/**
* Test scaffolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered stream ****
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
// **** read and split input line ****
String[] arr = input.readLine().split(",");
// **** close buffered stream ****
input.close();
// **** populate the binary tree ****
TreeNode root = populateBT(arr);
// ???? inOrder binary tree traversal (recursive approach) ????
System.out.print("main <<< inOrder: ");
inOrder(root);
System.out.println();
// ???? inOrder binary tree traversal (iterative approach) ????
System.out.print("main <<< inOrderIterative: ");
inOrderIterative(root);
System.out.println();
// **** determine if a valid BST ****
System.out.println("main <<< isValidBST1: " + isValidBST1(root));
// **** determine if a valid BST ****
System.out.println("main <<< isValidBST2: " + isValidBST2(root));
// **** determine if a valid BST ****
System.out.println("main <<< isValidBST0: " + isValidBST0(root));
// **** determine if a valid BST ****
System.out.println("main <<< isValidBST: " + isValidBST(root));
}
This is the test scaffolding that I generated. You do not need to develop the test scaffolding when solving problems in LeetCode or most similar platforms (i.e., HackerRank). I generate such scaffoldings because I like to develop the solution on my computer using the tools and libraries that I employ for work.
After reading the data we populate the binary tree. We then display the binary tree two times. Of interest is the iterative approach. The rest of the code seems to be self explanatory.
/**
* Display node values in a binary tree in order traversal.
* Iterative approach.
* !!! NOT PART OF SOLUTION !!!
*/
static void inOrderIterative(TreeNode root) {
// **** sanity check(s) ****
if (root == null)
return;
// **** initialization ****
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
// **** traverse the binary tree ****
while (node != null || stack.size() > 0) {
// **** save node and left children of node ****
while (node != null) {
stack.push(node);
node = node.left;
}
// **** pop next node ****
node = stack.pop();
// **** display node value ****
System.out.print(node.val + " ");
// **** to visit right node (if needed) ****
node = node.right;
}
}
The inOrderIterative() method is one of the common iterative approaches to traverse a binary tree.
We start by checking if the binary tree is empty. We then perform an initialization. In this method we will use a queue. We start by assigning the root argument to the node variable. We then enter a loop which implements the core logic.
In the loop we take the node and push it into the stack. We then set the node variable to the left child and repeat the process until we reach the last left child.
We pop the top element from the stack. We display the value. We then assign the right node to the node variable because we need to traverse the right sub tree.
Note that what we are implementing is an in order binary tree traversal. If interested in the recursive counterpart, you can find it in the GitHub repository associated with this post.
Please make sure you can follow the logic. We will use it to solve the problem at hand.
If you wish to learn more about recursive binary tree traversals, just enter a search in your web browser. There are many articles that cover such topic. Of interest you might find interesting to read Inorder Tree Traversal without Recursion by GeeksforGeeks.
/**
* Recursive call.
* Makes use of stack.
*
* Runtime: 1 ms, faster than 29.59% of Java online submissions.
* Memory Usage: 38.7 MB, less than 46.91% of Java online submissions.
*/
static boolean isValidBST1(TreeNode root) {
// **** sanity check(s) ****
if (root == null)
return true;
// **** initializion ****
Stack<TreeNode> stack = new Stack<>();
TreeNode prev = null;
// **** loop thorugh the binary tree ****
while (root != null || !stack.isEmpty()) {
// **** push node into stack ****
while (root != null) {
// ???? ????
System.out.println("<<< push root: " + root.toString());
// **** ****
stack.push(root);
// **** ****
root = root.left;
}
// ???? ????
System.out.println("<<< stack bottom -> " + stack.toString());
// **** pop element ****
root = stack.pop();
// ???? ????
System.out.println("<<< pop root: " + root.toString());
// **** check if invalid root value ****
if (prev != null && root.val <= prev.val) {
// ???? ????
System.out.println("<<< root: " + root.toString() + " <= prev: " + prev.toString() + " !!!");
// **** invalid BST ****
return false;
}
// **** set previous node ****
prev = root;
// ???? ????
System.out.println("<<< prev: " + prev.toString());
// **** visit right subtree ****
root = root.right;
}
// **** valid BST ****
return true;
}
This is the solution (perhaps with some minor editing) that I was the subject of the Reddit post. As you can see, it performs an iterative binary tree traversal. You can compare it to the code shown earlier in this post.
The difference is that we need to validate the value of the current node with the previous one. It works well.
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 4,665 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
john.canessa@gmail.com