As you might know, I work on 2-hour blocks. At the end of a block I go upstairs and get something to drink. I chat with my wife for a few minutes and then head downstairs to my office for the next 2-hour block. I just got back and was about to start a new task when I noticed that I had not finished a post I started earlier today. Will finish it right now and will post it. Then I will move on to the next task.
This morning we woke up to a balmy 11 F degrees. The good thing about the COVID-19 pandemic is that we can work from home and do not have to deal with the car and parking. I fully understand that is nothing to what other people are going through. Hopefully we will be getting a vaccine in the next few months. If all goes well we might start going back to something that resembles how things were before the pandemic.
OK, enough chit chat. Let’s get to the main subject of this post.
Earlier this morning I randomly selected LeetCode problem 285 Inorder Successor in BST.
Given a binary search tree and a node in it, find the in-order successor of that node in the BST. The successor of a node p is the node with the smallest key greater than p.val. MY EDITORIAL: In other words it seems we are looking for the next node after p in an in-order tree traversal. Note: o If the given node has no in-order successor in the tree, return null. o It's guaranteed that the values of the tree are unique.
I am very fond of LeetCode and HackerRank. That said, I completely dislike when problems are poorly described. No matter how complicated or simple the requirements for a project / task are, we need to have a simple description that helps software engineers and system architects generate the best possible approach. In most problems it seems that half the battle is to understand what the requirements are. Perhaps I am being too harsh with this problem, but the requirements could be stated in a simpler language.
The description starts quite simple and direct to the point. Then the second sentence made me think that perhaps there was something else behind the scenes.
The editorial is not in the original requirements. I just wrote them in my edited version to make it clear that is all what the problem requires.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
}
}
The TreeNode class is quite popular for binary trees at LeetCode. Like their consistency. The signature for the function / method makes sense. We will be given a BST and a node p in the tree. The idea is to return the next node in the tree (if any).
As usual I will solve the problem on my computer and will paste the answer on the LeetCode site. I will use Java on a Windows 10 computer and the VSCode IDE.
2,1,3 1 main <<< arr: [2, 1, 3] main <<< inOrder: 1 2 3 main <<< pVal: 1 main <<< p: 1 main <<< output: 2 5,3,6,2,4,null,null,1 6 main <<< arr: [5, 3, 6, 2, 4, null, null, 1] main <<< inOrder: 1 2 3 4 5 6 main <<< pVal: 6 main <<< p: 6 main <<< output: null 2,null,3 2 main <<< arr: [2, null, 3] main <<< inOrder: 2 3 main <<< pVal: 2 main <<< p: 2 main <<< output: 3 5,3,6,1,4,null,null,null,2 4 main <<< arr: [5, 3, 6, 1, 4, null, null, null, 2] main <<< inOrder: 1 2 3 4 5 6 main <<< pVal: 4 main <<< p: 4 main <<< output: 5 20,8,22,4,12,null,null,null,null,10,14 8 main <<< arr: [20, 8, 22, 4, 12, null, null, null, null, 10, 14] main <<< inOrder: 4 8 10 12 14 20 22 main <<< pVal: 8 main <<< p: 8 main <<< output: 10 20,8,22,4,12,null,null,null,null,10,14 10 main <<< arr: [20, 8, 22, 4, 12, null, null, null, null, 10, 14] main <<< inOrder: 4 8 10 12 14 20 22 main <<< pVal: 10 main <<< p: 10 main <<< output: 12
I have a set of test cases. Most of them came from LeetCode. I like to experiment as I am solving the problem and after the solution is accepted to improve on it.
The first line is a breadth first traversal on the nodes of a BST. The second line contains the value for the node of interest. We need to return the next node (if any) after the one holding the specified value when performing a BST in-order traversal.
Our test scaffolding seems to generate an array of integers with the input data for the BST nodes.
The BST appears to be generated and an in order traversal is used to display the nodes. As expected they are in ascending order and the number of nodes matches the number and values in the array. All appears to be well so far.
Next the value for the node p is displayed. It seems to match the specified input.
We probably look for the node with the specified value and display its value. At this point we just need to call the function / method we need to develop, compute the returned value and display it.
/**
* Test scaffolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open a buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read the nodes provided in a breadth first serach format ***
String[] strArr = br.readLine().trim().split(",");
// *** read the value of the node of interest ****
int val = Integer.parseInt(br.readLine().trim());
// **** close the buffered reader ****
br.close();
// **** create and populate integer array (may contain null) ****
Integer[] arr = new Integer[strArr.length];
for (int i = 0; i < strArr.length; i++) {
if (strArr[i].equals("null"))
arr[i] = null;
else
arr[i] = Integer.parseInt(strArr[i]);
}
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** create and populate binary tree ****
TreeNode root = populateTree(arr);
// ???? ????
System.out.print("main <<< inOrder: ");
inOrder(root);
System.out.println();
// ???? ????
// System.out.print("main <<< reverseOrder: ");
// reverseOrder(root);
// System.out.println();
// ???? ????
System.out.println("main <<< pVal: " + val);
// **** look for the specified node in the BST
// (should always be found) ****
TreeNode p = find(root, val);
// ???? ????
System.out.println("main <<< p: " + p.val);
// **** compute and display the result ****
System.out.println("main <<< output: " + inorderSuccessor(root, p));
}
The code for the test scaffolding should match our previous observations. Note that the test scaffolding is NOT PART OF THE SOLUTION. If you develop the code on the LeetCode site you do not need a test scaffolding.
If seems we read the two input lines.
With the collected data we assign it to an array and an integer.
The contents of the array are used to generate the associated BST. We then display the contents of the BST while performing an in-order traversal.
We display the value of the p node and find it in the BST we just generated.
We are now ready to call the function / method we need to develop and display the returned value.
Please note that what we have been asked to do is to return the node that follows the value of the p node in an in-order traversal. In the second example, we are looking for the node that follows the 6. On the fourth example we are required to return the node following the one with a value of 4.
/**
* Find the in-order successor of that node in the BST.
* Entry point for recursive call.
*
* Runtime: 2 ms, faster than 50.36% of Java online submissions.
* Memory Usage: 40 MB, less than 30.86% of Java online submissions.
*/
static TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
// **** initialization ****
TreeNode[] arr = new TreeNode[1];
// **** find successor ****
inorderSuccessor(root, p, arr);
// **** return successor ****
if (p.val != arr[0].val)
return arr[0];
else
return null;
}
We are using the required function as an entry point to perform an in order tree traversal implemented in a second function / method we will visit shortly.
We declare a one element array in which we will receive the node that follows the p node in an in-order tree traversal. The work is performed by the recursive function we invoke. When all is set and done we process the value in the array and returned the proper value.
/**
* Find the in-order successor of that node in the BST.
* Returns previous visited node.
* Recursive call.
*/
static void inorderSuccessor(TreeNode root, TreeNode p, TreeNode[] arr) {
if (root != null) {
// **** traverse left sub tree ****
inorderSuccessor(root.left, p, arr);
// **** flag we found node p ****
if (root.val == p.val) {
arr[0] = root;
}
// **** flag we found next node after p ****
else if (arr[0] != null && arr[0].val == p.val) {
arr[0] = root;
}
// **** traverse right sub tree ****
inorderSuccessor(root.right, p, arr);
}
}
This implementation follows a typical in-order tree traversal procedure. The recursive parts are typical so we can skip over them.
Of interest is what we do when we visit each node in order. When we find the p node we save it in the array. This states that we encountered the p node. In the next pass we should encounter the next node. We check that we already saved the p node so we update it with the value of the next node.
The reason to save the p node is to flag that we have already visited p and on the next pass (if any) we will be visiting the next node which we will save so we can extract it when we are done.
Note that the p node might be the last node visited during the tree traversal. In that case we will not have a next node to update the arr array. This is addressed in the entry function / method. The requirements state that if there is no next node in the BST we need to return null.
This code implements a BST tree traversal. The execution time is O(n) because we visit all nodes in the tree.
Note that the GitHub repository includes all the functions / methods used by the test scaffolding.
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 5,038 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
Regards;
John
john.canessa@gmail.com