Good morning! Yesterday my wife and I grilled some beef, made French fries in an iron pan in the grill and topped it off with some grilled asparagus. We spend the rest of the day making some profiteroles. We explored using a different flower in order for the pastry to not rise much (our oldest son prefers them that way), but the flavor changed. My wife is in charge of the pastry cream which she made. When all was set and done we delivered them to my son who lives in a different suburb of the Twin Cities of Minneapolis and St. Paul.
While driving back, my wife and I were talking about how the social life of people has changed since the COVID-19 pandemic started. We and most of the people when know, are taking care of themselves and others by following social distancing rules, wearing masks and gloves and lately even wearing goggles. We are very tired of the pandemic, but like most people, we need to continue to observer the rules until vaccines are approved and become available to all.
I selected a problem in LeetCode but was not allowed to see it. It seems that for some problems you need to purchase a Premium membership. It seems 
that price is currently discounted down to 159 USD. The membership is for a year. You can get a monthly membership, but as usual you end paying more than if you get the yearly program.
A person was supposed to arrive today around 08:00 AM to redo the grout in the shower of our bathroom. It is about 09:15 AM and as far as I can tell, no show yet. We have in a pallet sitting in our garage with new tiles and other construction materials to remodel the bathroom, but due to the COVID-19 pandemic, we are just going to change the grout and faucet in the shower and wait for next year to proceed with the remodeling project.
It is 09:50 AM and the person just arrived. We are all wearing masks and some windows are open to have fresh air flow on the first floor.
Let’s get to the main subject of this post. I searched LeetCode with the tag “recursion”. It seems that actual recursive problems appeared. I am planning on working on all of them during the next few weeks.
Today I selected 938. Range Sum of BST which is rated as Easy by LeetCode. If interested take a look at the description at LeetCode. It is a good idea to always give it a try on your own before looking at the entire solution.
As usual I like to develop software using the tools I am comfortable with and using my computer systems. This does not mean that I only use a single set of tools. Now and then I read about a tool and give it a try. If I like it I will start using it. This problem will be tackled using the Java programming language using VSCode IDE on a Windows 10 machine. I used to be a fan on Eclipse and before that JetBrains, but with time I have migrated to VSCode. As you might know VSCode supports Git. I prefer to issue the Git commands from a command prompt. I like to follow and understand what I am doing. Git is somewhat extensive and the best way to keep up and learn new tricks is to use it directly.
Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive). The binary search tree is guaranteed to have unique values.
We are given a BST and we are told to return the sum of the values of all nodes within the specified range [L : R].
10,5,15,3,7,null,18 7,15 main <<< inOrder: 3 5 7 10 15 18 main <<< L: 7 R: 15 main <<< sum: 32 10,5,15,3,7,13,18,1,null,6 6,10 main <<< inOrder: 1 3 5 6 7 10 13 15 18 main <<< L: 6 R: 10 main <<< sum: 23
LeetCode provides two examples. I manipulated the data to make it easier for my test scaffolding. Note that the values for the nodes in the BST are given in a level order. In addition in each of the examples, one child has a null value, so we need to skip it when populating the BST.
Go ahead and draw the BSTs on a piece of paper and get a graphical view of what needs to happen. Will pause until you are ready to continue …
The idea is to somewhat traverse the BST and add to the sum the values of the nodes that are within the specified range. We will use a modified in-order tree traversal approach.
/**
* 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 rangeSumBST(TreeNode root, int L, int R) {
}
}
This is the description of the nodes used by LeetCode for this problem. You can find it in the right side of the page describing the problem. The rangeSumBST() function in the solution is where we need to generate our solution. Since we will use a homegrown approach, we will develop the code on our computer and then copy the body of the function into LeetCode. The body is the only part required by LeetCode. The rest of the code is just for our test scaffolding.
/**
* Test scaffolding.
*/
public static void main(String[] args) {
// **** root for BST ***
TreeNode root = null;
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read the data for the BST ****
String[] arr = sc.nextLine().split(",");
// **** populate the BT in level order (supports 'null' values) ****
root = populateTree(arr);
// ???? inorder traversal (check the BT) ????
System.out.print("main <<< inOrder: ");
inOrder(root);
System.out.println();
// **** read the L & R values ****
String[] lAndr = sc.nextLine().split(",");
int L = Integer.parseInt(lAndr[0]);
int R = Integer.parseInt(lAndr[1]);
// ???? ????
System.out.println("main <<< L: " + L + " R: " + R);
// **** close scanner ****
sc.close();
// **** generate and display the sum ****
System.out.println("main <<< sum: " + rangeSumBST(root, L, R));
}
We start by defining the empty root of our BST. We open the scanner and read the first line. We split and populate an array which we will use to fill the BST. Note that to make sure the BST was properly build, we will perform an in-order traversal. Later on we will use a similar approach to solve the actual problem.
Next we read the left and right limits. With that information in hand, we can tackle solving the problem. We will display the resulting sum which in the two cases matches the solutions on the LeetCode site.
/**
* Definition for a binary tree node.
*/
class TreeNode {
// **** members ****
int val;
TreeNode left;
TreeNode right;
// **** constructor ****
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 working on my computer, I need a clean copy of the class TreeNode. No changes have been made.
/**
* This method populates a BT in level order as specified by the array.
*/
static TreeNode populateTree(String[] arr) {
// **** root for the BT ****
TreeNode root = null;
// **** ****
Queue<TreeNode> q = new LinkedList<TreeNode>();
// **** traverse the array of values inserting the nodes into the BT ****
for (String strVal : arr)
root = insertValue(root, strVal, q);
// **** clear the queue ****
q = null;
// **** return the root of the BT ****
return root;
}
This function was used in previous posts. I decided to look it up in GitHub and just copy the function here. After finding the code for Longest Univalue Path in my blog I navigated to the associated GitHub repository to find out that the posted software version was incomplete. Not sure how that happened. I went 
to my blog and used it to update my local copy using VSCode. After testing it I updated the associated GitHub repo.
The populateTree() function uses a String array with the values for the BST and null values. IN both cases there is a single null value. Thus function mimics a breadth first search approach. Note that the function calls the insertValue() function.
/**
* Enumerate which child in the node at the head of the queue
* should be updated.
*/
enum Child {
LEFT,
RIGHT
}
Before looking at the insertValue() function we declare the enum Child. We will use it to indicate if we are processing the left or right child of a node.
// **** child turn to insert on node at head of queue ****
static Child insertChild = Child.LEFT;
/**
* This method inserts the next value into the specified BT.
* This method is called repeatedly from the populateTree method.
*/
static TreeNode insertValue(TreeNode root, String strVal, Queue<TreeNode> q) {
// **** node to add to the BT in this pass ****
TreeNode node = null;
// **** create a node (if needed) ****
if (!strVal.equals("null"))
node = new TreeNode(Integer.parseInt(strVal));
// **** BT is empty (this is 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 needed) ****
if (node != null)
q.add(node);
// **** return the root of the BT ****
return root;
}
Note that we start by declaring a variable outside the insertValue function. Will use it to flag which child in the current BST node we are inserting. If the node is not available we create it. We then decide if we are inserting the value as a left or a right child. Note that a queue is used to select the next node to insert. Once again, this insertion mechanism is outside the scope of the solution for the problem.
/**
* Traverse the specified BT displaying the values in order.
* This method is used to verify that the BT 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);
}
We are going to traverse our BST using this function. The results should be in ascending order. Note that we first descend in to the lowest value in the BST. From then on we visit the root and use the opportunity to display its value. Then we visit the right child. The function is recursive and it displays the values of the BST in order. If needed, take some time to understand what is going on.
/**
* Given the root node of a binary search tree,
* return the sum of values of all nodes with value
* between L and R (inclusive).
*/
static int rangeSumBST(TreeNode root, int L, int R) {
// **** initialize sum ****
int sum = 0;
// **** base case ****
if (root == null)
return 0;
// **** traverse left tree ****
if (root.left != null)
sum += rangeSumBST(root.left, L, R);
// **** update sum ****
if ((root.val >= L) && (root.val <= R))
sum += root.val;
// **** traverse right tree ****
if (root.right != null)
sum += rangeSumBST(root.right, L, R);
// **** ****
return sum;
}
Finally we are ready to tackle the problem by coding the rangeSumBST() function. As we previously discussed, the approach is similar to in-order traversal. We traverse the left child until we get to a null value. When we pop the recursion stack, we end in the node with the lowest value (in this case 3 if we are looking at the first example). At this point we would need to determine if the sum needs to be updated. We check if 3 is greater that L or less than R; in this case 7 and 15 respectively. Since we do not need to do so, we proceed to traverse the right node.
Sooner or later we will hit the node with value 7. We will add such value to our running sum. I missed to place print statements showing the value of a node and the running sum. It is much easier to use the debugger and watch how the value is skipped if not in range, and how the sum is generated.
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 1750 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
Twitter: @john_canessa