It is a gloomy day in the Twin Cities of Minneapolis and St. Paul. The good thing is that we have about two days until Thanksgiving Day 2020. This year we are cooking an 11 lbs. turkey. Typically my wife and I make an 18+ lbs. bird. Not only that but we are dropping half of it at our granddaughters place. On Thanksgiving Day we will be connecting with family via Jitsi and Skype.
Earlier today I picked LeetCode problem 98 – Validate Binary Search Tree. Due to the fact that I like to solve problems on my computer, I have been developing auxiliary code for the test scaffoldings. Having the ability to check if a binary tree is a Binary Search Tree might come handy.
Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees.
The requirements are quite straightforward and succinct. We are given a binary tree and we need to determine if the tree is a BST (https://en.wikipedia.org/wiki/Binary_search_tree) or not. LeetCode provides some points that we should consider when solving the problem.
/**
* 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 boolean isValidBST(TreeNode root) {
}
}
The TreeNode class is typically used by LeetCode for most of their binary tree problems. We are also presented with the format of the isValidBST() method we need to implement.
Before we dive into the problem, I want to state that I will be developing the solution in my computer. Due to this fact, I will have to develop a test scaffolding. When I have a candidate for testing, I will copy it to the LeetCode website and see if it will pass the tests. In addition to just passing the tests, in most occasions, I like to modify my code to see if I can get better performance.
I will use Java and the VSCode IDE on a Windows 10 computer. Given the fact that I am using Java the solution should work on any other platform.
2,1,3 main <<< isValidBST0: true main <<< isValidBST: true 5,1,4,null,null,3,6 main <<< isValidBST0: false main <<< isValidBST: false 10,5,15,null,null,6,20 main <<< isValidBST0: false main <<< isValidBST: false -2147483648,null,2147483647 main <<< isValidBST0: true main <<< isValidBST: true
It seems that our test scaffolding will read the data for the binary tree. Typically I display the data to make sure all is well. I wrote a method to perform an in order traversal of the binary tree but it seems that at some point I deleted it from the test scaffolding. If interested in that method, the code is in the GitHub repository associated with this post.
It seems we have two implementations of the solution. Their results appear to match (that is encouraging).
/**
*
*/
class TreeNode {
// **** class members ****
int val;
TreeNode left;
TreeNode right;
// **** constructor(s) ****
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;
}
}
This is my implementation of the TreeNode class. This is not needed for the solution but I require it because of the test scaffolding.
As usual I have added the toString() method. I do not believe it is used in the test scaffolding as it sits in this post.
/**
* 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);
// **** determine if valid BST ****
System.out.println("main <<< isValidBST0: " + isValidBST0(root));
// **** determine if valid BST ****
System.out.println("main <<< isValidBST: " + isValidBST(root));
}
The test scaffolding is simple. We read the line with the level order traversal of the binary tree. The values are split and then passed to a method that will use such data to create a binary tree. This is not part of the solution because LeetCode will provide the binary tree for testing.
Once the binary tree is ready, we call two methods with different implementation. I was going to have a third implementation between the first and second, but due to similarities (and time constraints) I decided to skip it.
/**
* Given a binary tree, determine if it is a valid binary search tree (BST).
*
* Runtime: 1 ms, faster than 29.86% of Java online submissions.
* Memory Usage: 39 MB, less than 16.71% of Java online submissions.
*/
static boolean isValidBST0(TreeNode root) {
// **** sanity checks ****
if (root == null)
return true;
// **** initialization ****
List<Integer> vals = new ArrayList<Integer>();
// **** in order tree traversal ****
traverse0(root, vals);
// **** sanity check ****
if (vals.size() == 1)
return true;
// **** traverse list of vals ****
for (int i = 1; i < vals.size(); i++) {
if (vals.get(i - 1) >= vals.get(i))
return false;
}
// **** valid BST ****
return true;
}
The isValidBST0() method is our first implementation. The idea is to use memory to populate with the contents of an in order traversal. Once we have the values of the nodes in order, we can traverse the data structure and check for values out of order. As soon as we find such condition we know the binary tree is not a BST.
We start by checking if the root is null. Then we allocate an array list to store the values of the nodes as we perform an in order tree traversal. As I mentioned earlier in this post, while I was implementing this approach, I figured it could have been easier to use a stack instead of an array list. If interested, go ahead and implement it. You should submit it to LeetCode to check performance. My estimate is that it might be somewhat faster than the array list implementation. If you do, please send me a message with your findings.
The traverse0() method is used to perform the in order tree traversal.
When that is done, we check if our binary tree has a single node. If so we can return true.
If the binary tree contains more than one node, we need to traverse the array list (or the stack) checking if the values are in an ascending order and there are no duplicates. If we find an element out of order, then we know the binary tree is not a BST. If the program executes past the loop, we know the binary tree is a BST.
/**
* Recursive call
*/
static void traverse0(TreeNode node, List<Integer> vals) {
// **** visit left sub tree (if needed) ****
if (node.left != null)
traverse0(node.left, vals);
// **** add node value to list ****
vals.add(node.val);
// **** visit right sub tree (if needed) ****
if (node.right != null)
traverse0(node.right, vals);
}
This is the recursive call. We visit the left sub tree, then the current node. At this time we only have to add the value to the array list. Finally we visit the right sub tree. This approach was accepted by LeetCode. You can see the performance in the comments section in the code.
/**
* Given a binary tree, determine if it is a valid binary search tree (BST).
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 38.4 MB, less than 78.20% of Java online submissions.
*/
static boolean isValidBST(TreeNode root) {
// **** is valid flag ****
boolean[] isValid = new boolean[] {true};
// **** traverse tree ****
traverse(root, new Integer[] {null}, isValid);
// **** return result ****
return isValid[0];
}
A different approach would be to not use additional space (the array list or stack). We could achieve that by performing some checks and computations as we traverse the binary tree.
We start by initializing a variable (actually a boolean array of one value). Note that we also pass an integer array with one value as the second argument. The isValid variable will be used to flag if the binary tree is NOT a BST. I had to add the second argument because without it I would have had the need for a fourth argument. This will become clear when we visit the recursive code associated with this method.
/**
* Recursive call.
*/
static void traverse(TreeNode node, Integer[] prevVal, boolean[] isValid) {
if (node != null) {
// **** traverse left sub tree ****
traverse(node.left, prevVal, isValid);
// **** set flag to false (if needed) ****
if (prevVal[0] != null && prevVal[0] >= node.val) {
isValid[0] = false;
}
// **** save this value ****
prevVal[0] = node.val;
// **** traverse right sub tree ****
traverse(node.right, prevVal, isValid);
}
}
This is the recursive method that performs an in order traversal of the binary tree. We start by traversing the left sub tree. We then visit the root node and perform some operations. Finally we traverse the right sub tree.
I will call your attention to the code that executes when visiting the root node. The idea is to remember the value of the node previously visited. And compare it against the value of the current node. If the previous value is greater or equal than the value of the current node, this is not a BST. We then save the value of the node for the next pass.
The issue is that if we cannot differentiate the value of the first node (no previous yet), we could not figure out is there is an issue with the first two nodes. I experimented (knowing it would fail) with assigning INTEGER_MIN to prevVal in the calling function. Go back and check the last test. It was designed by LeetCode to create problems with the type of approach we are using. The simple thing was to set the Integer variable (it was an int) to null. The solution was accepted. The execution time is in the comments section of the function.
I had a good time experimenting and learning with this problem. 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,547 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
john.canessa@gmail.com