Earlier today I read the article “Changing the clocks is a bad idea — and it should end, sleep experts say” by Jen Smith, CNN. The article makes a case for the USA to eliminate daylight savings time. It seems there is enough science behind the idea.
I am a morning person. I have a wake up alarm in my smart phone to wake up at 06:00 AM every day. Most of the time I get up about an hour early. Of course, in the evenings my wife and I are ready to hit the sack around 08:00 PM. At the start of summer the sun is up before 06:00 AM. At the start of winter, it is dark around 04:30 PM.
The article provides some statistics about saving energy. It seems the idea is no longer working. Of course, in order to increase sales, hospitality 
businesses promote it. It is nice to go out after work for food and drinks with friends and family. There is plenty of light to use the patios. There is nothing wrong with this picture.
On the other hand, when time changes due to daylight savings, it seems the number of accidents and deaths increases. That is not good.
I was in the navy for seven years. Now and then, depending on seniority, you have to be on duty. The shifts rotate, but you will get some at night, early morning hours, and morning. That has a bad effect in your circadian rhythm.
Perhaps it would not be a bad idea is businesses stop lobbying for daylight savings and lawmakers eliminate it. There are many countries in the world that do not use daylight savings.
I decided to give a shot at LeetCode problem 783 “Minimum Distance Between BST Nodes”. If interested take a look at the requirements for the problem. Spend some time attempting a solution. If things do not work well, go ahead and take a peek at my solution written in Java.
Given a Binary Search Tree (BST) with the root node root, return the minimum difference between the values of any two different nodes in the tree.
We are given a BST and are supposed to get the minimum difference between any two different nodes. Spend a minute understanding what the requirements are. In a nutshell we need to compute the difference between all nodes and select the smallest. Remember we are dealing with a BST.
The size of the BST will be between 2 and 100. The BST is always valid, each node's value is an integer, and each node's value is different. This question is the same as 530: https://leetcode.com/problems/minimum-absolute-difference-in-bst/
The limits for the BST are provided by LeetCode. Note than there seems to be a different problem which is very similar (if not the same) as this one. I will see if I can remember and give it a try tomorrow.
/**
* 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 int minDiffInBST(TreeNode root) {
}
}
Since we are dealing with a BST we need to know the data that represents the nodes. LeetCode provides us with a description of the TreeNode class.
The entry point for our solution is the function named minDiffInBST(). As you know, I prefer to develop the solution using my computer and software development tools. For this reason I need to develop a test scaffolding. Yes, it represents additional work, but there is always the possibility of learning something new. If not, it serves as an opportunity to review.
8,2,12 main <<< inOrder: 2 8 12 main <<< minDiffInBST: 4 8,2,12,1 main <<< inOrder: 1 2 8 12 main <<< minDiffInBST: 1 10,5,15,2,9,11,25 main <<< inOrder: 2 5 9 10 11 15 25 main <<< minDiffInBST: 1 4,2,6,1,3,null,null main <<< inOrder: 1 2 3 4 6 main <<< minDiffInBST: 1 30,15,50,10,20,45,55 main <<< inOrder: 10 15 20 30 45 50 55 main <<< minDiffInBST: 5 90,69,null,49,89,null,52,null,null,null,null main <<< inOrder: 49 52 69 89 90 main <<< minDiffInBST: 1
LeetCode provides an example. One of the test cases comes from the problem. The test scaffolding appears to read in the data for the BST, display the values in-order, and return the result. My solution was accepted by LeetCode.
/**
* 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;
}
}
Since I am developing the solution on one of my Windows 10 machines using Java and the VSCode IDE, I do need a copy of the TreeNode class. The class is a replica of what LeetCode used in this problem.
/**
* Test scaffolding.
*/
public static void main(String[] args) {
// **** root of BST ****
TreeNode root = null;
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read into a string array the node values for the BST ****
String[] arr = sc.nextLine().split(",");
// **** close scanner ****
sc.close();
// **** populate the BST in level order ****
root = populateTree(arr);
// **** inorder traversal (make sure all is well with it) ****
System.out.print("main <<< inOrder: ");
inOrder(root);
System.out.println();
// **** compute and display the minimum difference between node values ****
System.out.println("main <<< minDiffInBST: " + minDiffInBST(root));
}
We start by declaring the root node for the BST. We open a scanner and read the line with the values for the nodes. Our code is able to process the ‘null’ values. Note that the data for the BST is provided in level order (breadth first). Since we are done with the scanner we go ahead and close it. I like to free resources as soon as they are not needed.
We then populate the BST. To make sure we performed the task with some degree of confidence, we will display the BST by performing an in-order traversal. As you know, I try to check my steps to catch issues as early as possible. If you are still thinking about your approach, this is a good time to go back to the output in the test cases and try to come up with a solution when looking at the in-order traversal output. We can pause for a few now …
We then call the function that returns the required value and display it on the command prompt.
/**
* This function populates a BST in level order as
* specified by the array.
* This function supports 'null' values.
*/
static TreeNode populateTree(String[] arr) {
// **** root for the BT ****
TreeNode root = null;
// **** auxiliary queue ****
Queue<TreeNode> q = new LinkedList<TreeNode>();
// **** traverse the array of values inserting nodes
// one at a time into the BST ****
for (String strVal : arr)
root = insertValue(root, strVal, q);
// **** clear the queue (the garbage collector will do this) ****
q = null;
// **** return the root of the BST ****
return root;
}
This is the function that populates the BST. We start with a root for the tree and set it to null. We declare a queue which will be used to insert nodes in the BST. We then loop once per value in the array populating the BST. When done we free the queue (there is really no need because the garbage collector will take care of it) and return the root of the populated BST.
/**
* Enumerate which child in the node at the head of the queue
* (see populateTree function) should be updated.
*/
enum Child {
LEFT,
RIGHT
}
We could just use a value to flag the left and right children of a node in the BST, but decided to declare an enum.
// **** child turn to insert on node at head of queue ****
static Child insertChild = Child.LEFT;
/**
* This function inserts the next value into the specified BST.
* This function is called repeatedly from the populateTree method.
* This function supports 'null' value.
*/
static TreeNode insertValue(TreeNode root, String strVal, Queue<TreeNode> q) {
// **** node to add to the BST in this pass ****
TreeNode node = null;
// **** create a node (if needed) ****
if (!strVal.equals("null"))
node = new TreeNode(Integer.parseInt(strVal));
// **** check is the BST is empty (this becomes the root node) ****
if (root == null)
root = node;
// **** add node to left child (if possible) ****
else if (insertChild == Child.LEFT) {
// **** add this node as the left child ****
if (node != null)
q.peek().left = node;
// **** for next pass ****
insertChild = Child.RIGHT;
}
// **** add node to right child (if possible) ****
else if (insertChild == Child.RIGHT) {
// **** add this node as a right child ****
if (node != null)
q.peek().right = node;
// **** remove node from queue ****
q.remove();
// **** for next pass ****
insertChild = Child.LEFT;
}
// **** add this node to the queue (if NOT null) ****
if (node != null)
q.add(node);
// **** return the root of the BST ****
return root;
}
We set a variable to keep track of the current child node to populate. Remember that the values are in level order. A null just skips a child (left or right). Note that the queue is used as a place to hold a node until their children are populated or skipped with a null.
/**
* Traverse the specified BST displaying the values in order.
* This method is used to verify that the BST was properly populated.
*/
static void inOrder(TreeNode root) {
// **** end condition ****
if (root == null)
return;
// **** visit the left sub tree ****
inOrder(root.left);
// **** display the value of this node ****
System.out.print(root.val + " ");
// **** visit the right sub tree ****
inOrder(root.right);
}
This is the function we used to traverse the BST to make sure the values appear in ascending order. If not, we might have an incorrect tree or just messed up in the tree traversal. The tree traversal seems fine. The values are in ascending order. All seems to be working fine so far in our test scaffolding.
If you look at the output of the in-order traversal and think about the requirements, what we need to return is the minimum difference between two consecutive nodes in ascending order. One of the approaches to solve tree problems is to perform a modified in-order tree traversal.
// **** keep track of state in recursive call (part of the solution) ****
static int minDiff = 0;
static int prevVal = Integer.MAX_VALUE;
/**
* Given a Binary Search Tree (BST) with the root node root,
* return the minimum difference between the values of any
* two different nodes in the tree.
* This function implements the solution.
*/
static int minDiffInBST(TreeNode root) {
// **** initialization ****
minDiff = Integer.MAX_VALUE;
prevVal = Integer.MIN_VALUE;
// **** recursive call ****
minDiffTraversal(root);
// **** return result ****
return minDiff;
}
We declare two variables. The minDiff variable will hold the current minimum difference between nodes. We need to keep a running difference of the smallest value. In order to be able to get the difference between the value of the current node and the previous, we need to keep such value around. The prevVal variable holds the value of the previous node.
The minDiffInBST() function initializes the variables, makes a recursive call, and when done, returns the minimum difference of values in the BST.
/**
* Look for the minimum difference between any two node values.
* Based on in-order traversal.
* This is a recursive function.
* This function is part of the solution.
*/
static void minDiffTraversal(TreeNode root) {
// **** base case ****
if (root == null)
return;
// **** visit left tree ****
minDiffTraversal(root.left);
// **** update the minimum difference (if needed) ****
if (prevVal != Integer.MIN_VALUE) {
int diff = root.val - prevVal;
if (diff < minDiff)
minDiff = diff;
}
// **** update the previous value ****
prevVal = root.val;
// **** visit right tree ****
minDiffTraversal(root.right);
}
The minDiffTraversal() function mimics an in-order traversal recursive approach. The base case is the same. The visits to the left and right children are the same. The work is done when we visit a node. We need to update the minDiff variable after the first pass. On every pass we need to remember the value of the current node which will be the previous node in the next invocation of the function.
Using an in-order tree traversal is one of the go-to approaches to solve this type of problem.
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 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 1771 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
Twitter: @john_canessa