Hello there. It is another Sunday morning during the COVID-19 pandemic. The current temperature in the Twin Cities of Minneapolis and St. Paul is about 30F and is sunny. As soon as I finish with this post my wife and I will stop by Target to get some sundries.
Yesterday my wife and I met my older son at Costco in Minneapolis. We get together every other weekend at Costco to do groceries. My wife and I got a 35 lbs. of beef chuck cut. Once we got home we cut smaller manageable portions, put them in bags and placed them in the freezer. We left one portion out. We cut it into smaller pieces, cut some potatoes, onions, garlic and carrots. Put them in a tray in a 550 degree oven for 10 minutes. The beef browned quite nicely. We then put the items in a pressure cook with some water and left them cooking for 1 ½ hours. We served them in on a thin base of very hot brown rice. I had two large servings. It was delicious.
Earlier I selected LeetCode 1038 Binary Search Tree to Greater Sum Tree.
Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST. As a reminder, a binary search tree is a tree that satisfies these constraints: o The left subtree of a node contains only nodes with keys less than the node's key. o The right subtree of a node contains only nodes with keys greater than the node's key. o Both the left and right subtrees must also be binary search trees. Note: This question is the same as 538: https://leetcode.com/problems/convert-bst-to-greater-tree/ Constraints: o The number of nodes in the tree is in the range [1, 100]. o 0 <= Node.val <= 100 o All the values in the tree are unique (it is a binary search tree). o root is guaranteed to be a valid binary search tree.
The requirements indicate that we are working with a binary search tree. We need to traverse the tree performing some type of operation in order to 
update the values of the nodes in the tree.
It also seems like this problem is quite similar (if not identical) to LeetCode 538 Convert BST to Greater Tree. I will take a look at it after I finish this post.
While I am working on this computer, the Windows computer in which I solved this problem decided to install a Windows update and restart. It took a few minutes. It seems like it is done. Not sure why it took so long from Tuesday to install the updated.
/**
* 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 TreeNode bstToGst(TreeNode root) {
}
}
We need to develop the gstToGst() function. It looks like we will use the TreeNode class for the binary trees. That is great because we do not have to work on a different data structure each time we work with binary trees.
I will solve the problem using the Java programming language, on a Windows 10 machine and the VSCode IDE. Since I will use my own computer I will need to use my own test scaffolding. With time I have developed a test scaffolding to load and display trees that support the TreeNode class. In this post I will not cover all the functions I have developed for the test scaffolding. If you are interested you can take a look at the entire code for this post in the GitHub repository associated with this post.
4,1,6,0,2,5,7,null,null,null,3,null,null,null,8 main <<< root: 4 1 6 0 2 5 7 null null null 3 null null null 8 main <<< postOrder: 0 3 2 1 5 8 7 6 4 main <<< preOrder: 4 1 0 2 3 6 5 7 8 main <<< inOrder: 0 1 2 3 4 5 6 7 8 main <<< reverseInOrder: 8 7 6 5 4 3 2 1 0 main <<< Output: 30 36 21 36 35 26 15 null null null 33 null null null 8 0,null,1 main <<< root: 0 null 1 main <<< postOrder: 1 0 main <<< preOrder: 0 1 main <<< inOrder: 0 1 main <<< reverseInOrder: 1 0 main <<< Output: 1 null 1 1,0,2 main <<< root: 1 0 2 main <<< postOrder: 0 2 1 main <<< preOrder: 1 0 2 main <<< inOrder: 0 1 2 main <<< reverseInOrder: 2 1 0 main <<< Output: 3 3 2
It seems that we need to read a line holding a depth first representation of a binary tree. This is a compact way LeetCode tends to represent binary trees.
Our test scaffolding seems to read the representation and display it in a depth first search approach. The three examples are provided by LeetCode. Of interest is the first one because LeetCode provides a nice figure of the tree showing the initial and final values. Make user you look at the diagram because it seems to provide a hint on how to solve the problem.
After that our test scaffolding displays the input binary tree in four different ways. Note the last two. The in order traversal visits the nodes in ascending order while the reverseInOrder() function does the same but in reverse order. Such tree traversal is known as Reverse In Order. Go back to the diagram in the LeetCode site. It seems that we might take the reverseInOrder() function and use it as a base for our solution. Of course we have to first develop the reverseInOrder() function, but I did that prior to starting to solve the problem. Please take a few minutes and develop such function on your own. If you get stuck and need some inspiration, keep on reading this post and stop as soon as you get an idea on how to proceed.
The solution is generated and the resulting binary tree is displayed.
/**
* Test scaffolding.
* !!!! NOT PART OF SOLUTION !!!
*/
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read data for the BST ****
String[] arr = sc.nextLine().trim().split(",");
// **** close scanner ****
sc.close();
// **** populate the BST ****
TreeNode root = populateBT(arr);
// **** display the binary tree (sanity check) ****
System.out.println("main <<< root:");
System.out.print(bfsTraversal(root));
// **** ****
System.out.print("main <<< postOrder: ");
postOrder(root);
System.out.println();
// **** ****
System.out.print("main <<< preOrder: ");
preOrder(root);
System.out.println();
// **** ****
System.out.print("main <<< inOrder: ");
inOrder(root);
System.out.println();
// **** ****
System.out.print("main <<< reverseInOrder: ");
reverseInOrder(root);
System.out.println();
// **** generate the GST tree ****
TreeNode gst = bstToGst(root);
// **** display the GST tree ****
System.out.println("main <<< Output: ");
System.out.print(bfsTraversal(gst));
}
We open a scanner. Read the line and split the values into strings. The scanner is then closed because there is no more input for the problem.
We populate our binary tree and display it five times.
We then generate the required tree via the bstToGst() function and display the tree to make sure it matches the results provided by LeetCode. In the three examples the results seem to match.
/**
* Perform in-order tree traversal.
* This is a recursive function.
* !!!! NOT PART OF SOLUTION !!!
*/
public static void inOrder(TreeNode root) {
// **** check if we are done ****
if (root == null)
return;
// *** visit the left child ****
inOrder(root.left);
// **** display the data in this node ****
System.out.print(root.val + " ");
// **** visit the right child ****
inOrder(root.right);
}
The inOrder() function performs an in order tree traversal. This is a recursive function. We have a base case, followed by a recursive call to left of the tree, we then display the node value and finally we visit the with subtree. If new to this operation, verify what is going on. The results in a binary search tree are the values displayed in ascending order.
/**
* Perform reverse in-order tree traversal.
* This is a recursive function.
* !!!! NOT PART OF SOLUTION !!!
*/
public static void reverseInOrder(TreeNode root) {
// **** check if we are done ****
if (root == null)
return;
// **** visit the right child ****
reverseInOrder(root.right);
// **** display the data in this node ****
System.out.print(root.val + " ");
// *** visit the left child ****
reverseInOrder(root.left);
}
The reverseInOrder() function has a very similar structure and the inOrder() function. It is also recursive. The base case (check condition) is the same. Note that the only difference is that we traverse the children in different order. In this case we traverse the right subtrees before the left subtrees. That is how we obtain the values of the nodes in descending order.
If you are hesitating with a solution approach, go back to the description of the problem in the LeetCode web site and check the diagram with the results in blue. It seems that with some manipulations we might be able to use the reverseInOrder() function to get the desired results.
// **** sum of nodes ****
static int sum = 0;
We will use the sum variable to keep the sum of the nodes as we traverse the binary tree.
/**
* Entry call.
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 36.4 MB, less than 8.89% of Java online submissions.
*/
static TreeNode bstToGst(TreeNode root) {
// **** initialize sum ****
sum = 0;
// **** dfs ****
dfs(root);
// **** ****
return root;
}
We will use the bstToGst() function as the entry point for a recursive function. We initialize the sum, call the recursive function which will do most (if not all) of the work, and return the root of the same tree but with updated node values.
/**
* Recursive call.
*/
static void dfs(TreeNode root) {
// **** base case ****
if (root == null)
return;
// **** traverse right subtree ****
dfs(root.right);
// **** update node value ****
root.val += sum;
// **** update sum ****
sum = root.val;
// **** traverse left subtree ****
dfs(root.left);
}
The dfs() function is recursive. The base case is the same as in the reverseInOrder() function. The two recursive calls are in the same order. What we need to do is change the value of the nodes when we visit them. This is done with help from the sum variable.
All three examples worked. The solution was accepted. Timing for it is shown in the comment of the bstToGst() function.
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 3,627 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
E-mail: john.canessa@gmail.com