The temperature in the Twin Cities of Minneapolis and St. Paul continues to oscillate between negative and positive values in the Fahrenheit scale. The good thing is that we are around mid February. This year spring starts Saturday March 20. That is about 6 to 7 weeks from today.
I decided to give a try to LeetCode 1305 All Elements in Two Binary Search Trees problem.
Given two binary search trees root1 and root2. Return a list containing all the integers from both trees sorted in ascending order. Constraints: o Each tree has at most 5000 nodes. o Each node's value is between [-10^5, 10^5].
The requirements are nicely presented. We are provided two binary search trees and we need to return a sorted list with the values from both trees.
I started work on this problem yesterday evening but I had to stop. Early this morning I continued but left out what could have been the most elegant approach. As we know, both BSTs hold the data in sorted order. We could implement something like the last step of the merge sort algorithm and get our answer without additional sorts. This is something to think about. I would go for it but need to have breakfast and get ready for work.
I will tackle the problem using the Java programming language on a Windows 10 computer using the VSCode IDE. Of course, the simplest approach is to develop the code directly on the IDE provided by LeetCode.
Since we are not doing that, we will have to develop a test scaffolding to mimic what LeetCode has already provided. Note that such code IS NOT PART OF THE SOLUTION.
/**
* 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 List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
}
}
The signature for the method in question should not be a surprise based on the requirements.
We will use the TreeNode class as suggested. I have it already implemented in a separate file. If you solve the problem directly on the LeetCode site you will have no need to implement such class.
2,1,4 1,0,3 main <<< strArr1: [2, 1, 4] main <<< strArr2: [1, 0, 3] main <<< arr1: [2, 1, 4] main <<< arr2: [1, 0, 3] main <<< root1 levelOrder: 2 1,4 main <<< root2 levelOrder: 1 0,3 main <<< getAllElements: [0, 1, 1, 2, 3, 4] main <<< getAllElements: [0, 1, 1, 2, 3, 4] main <<< getAllElements: [0, 1, 1, 2, 3, 4] 0,-10,10 5,1,7,0,2 main <<< strArr1: [0, -10, 10] main <<< strArr2: [5, 1, 7, 0, 2] main <<< arr1: [0, -10, 10] main <<< arr2: [5, 1, 7, 0, 2] main <<< root1 levelOrder: 0 -10,10 main <<< root2 levelOrder: 5 1,7 0,2 main <<< getAllElements: [-10, 0, 0, 1, 2, 5, 7, 10] main <<< getAllElements: [-10, 0, 0, 1, 2, 5, 7, 10] main <<< getAllElements: [-10, 0, 0, 1, 2, 5, 7, 10] 5,1,7,0,2 main <<< strArr1: [] main <<< strArr2: [5, 1, 7, 0, 2] main <<< arr1: [] main <<< arr2: [5, 1, 7, 0, 2] main <<< root1 levelOrder: main <<< root2 levelOrder: 5 1,7 0,2 main <<< getAllElements: [0, 1, 2, 5, 7] main <<< getAllElements: [0, 1, 2, 5, 7] main <<< getAllElements: [0, 1, 2, 5, 7] 0,-10,10 main <<< strArr1: [0, -10, 10] main <<< strArr2: [] main <<< arr1: [0, -10, 10] main <<< arr2: [] main <<< root1 levelOrder: 0 -10,10 main <<< root2 levelOrder: main <<< getAllElements: [-10, 0, 10] main <<< getAllElements: [-10, 0, 10] main <<< getAllElements: [-10, 0, 10] 1,null,8 8,1 main <<< strArr1: [1, null, 8] main <<< strArr2: [8, 1] main <<< arr1: [1, null, 8] main <<< arr2: [8, 1] main <<< root1 levelOrder: 1 8 main <<< root2 levelOrder: 8 1 main <<< getAllElements: [1, 1, 8, 8] main <<< getAllElements: [1, 1, 8, 8] main <<< getAllElements: [1, 1, 8, 8] 1,2,null,3 4,null,5,6 main <<< strArr1: [1, 2, null, 3] main <<< strArr2: [4, null, 5, 6] main <<< arr1: [1, 2, null, 3] main <<< arr2: [4, null, 5, 6] main <<< root1 levelOrder: 1 2 3 main <<< root2 levelOrder: 4 5 6 main <<< getAllElements: [1, 2, 3, 4, 5, 6] main <<< getAllElements: [1, 2, 3, 4, 5, 6] main <<< getAllElements: [1, 2, 3, 4, 5, 6]
We are presented with two lines of integers. Each line is for the values of the nodes in our BSTs.
Apparently we read the lines and populate two String[] arrays. We then extract the integer values in two Integer[] arrays making sure we keep null values. One of the examples provides a null value. The reason is that the data is generated by a level order traversal of the BSTs.
After populating the BSTs we display the trees in a level order traversal. At this time we are ready to call the method of interest. Note we have three similar implementations. They all follow a similar approach. If you have time I suggest going for the approach that does not require sorting a list.
/**
* Test scafolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** initialization ****
String buffer;
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read data for first BST ****
buffer = br.readLine().trim();
// **** populate String[] ****
String[] strArr1 = null;
if (!buffer.equals(""))
strArr1 = buffer.split(",");
else
strArr1 = new String[0];
// **** read data for second BST ****
buffer = br.readLine().trim();
// **** populate String[] ****
String[] strArr2 = null;
if (!buffer.equals(""))
strArr2 = buffer.split(",");
else
strArr2 = new String[0];
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< strArr1: " + Arrays.toString(strArr1));
System.out.println("main <<< strArr2: " + Arrays.toString(strArr2));
// **** convert String[] to Integer[] ****
Integer[] arr1 = new Integer[strArr1.length];
for (int i = 0; i < arr1.length; i++) {
if (strArr1[i].equals("null"))
arr1[i] = null;
else
arr1[i] = Integer.parseInt(strArr1[i]);
}
// ???? ????
System.out.println("main <<< arr1: " + Arrays.toString(arr1));
// **** convert String[] to Integer[] ****
Integer[] arr2 = new Integer[strArr2.length];
for (int i = 0; i < arr2.length; i++) {
if (strArr2[i].equals("null"))
arr2[i] = null;
else
arr2[i] = Integer.parseInt(strArr2[i]);
}
// ???? ????
System.out.println("main <<< arr2: " + Arrays.toString(arr2));
// **** create and populate the root1 BST ****
BST root1 = new BST();
root1.root = root1.populate(arr1);
// ???? ????
System.out.println("main <<< root1 levelOrder:");
System.out.println(root1.levelOrder());
// **** create and populate the root2 BST ****
BST root2 = new BST();
root2.root = root1.populate(arr2);
// ???? ????
System.out.println("main <<< root2 levelOrder:");
System.out.println(root2.levelOrder());
// **** generate and display the list ****
System.out.println("main <<< getAllElements: " +
getAllElements1(root1.root, root2.root));
// **** generate and display the list ****
System.out.println("main <<< getAllElements: " +
getAllElements0(root1.root, root2.root));
// **** generate and display the list ****
System.out.println("main <<< getAllElements: " +
getAllElements(root1.root, root2.root));
}
The code seems to follow the steps we described while looking at the test cases. Note that one or perhaps both BSTs could be null. We need to make sure our test scaffolding is able to handle such condition.
/**
* Return a list containing all the integers from
* both trees sorted in ascending order.
*
* Runtime: 33 ms, faster than 12.92% of Java online submissions.
* Memory Usage: 41.4 MB, less than 95.16% of Java online submissions.
*/
static List<Integer> getAllElements1(TreeNode root1, TreeNode root2) {
// **** initialization ****
List<Integer> lst = new ArrayList<>();
PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> a - b);
// **** traverse root1 adding elements to the priority queue ****
traverse1(root1, pq);
// **** traverse root2 adding elements to the priority queue ****
traverse1(root2, pq);
// **** populate the list using the priority queue ****
while (!pq.isEmpty())
lst.add(pq.remove());
// **** return the list ****
return lst;
}
We initialize an array list and a priority queue. The idea is to avoid sorting the list.
We then traverse both BSTs adding the elements. We then add the elements to a list. The elements are coming out the priority queue in order. The list is then returned.
/**
* Traverse BST adding tree node values to the priority queue.
* Recursive O(n)
*/
static void traverse1(TreeNode root, PriorityQueue<Integer> pq) {
if (root != null) {
// **** visit left sub tree ****
traverse1(root.left, pq);
// **** ****
pq.add(root.val);
// **** visit right sub tree ****
traverse1(root.right, pq);
}
}
The method follows a depth first order traversal. The elements in the BST are added to the priority queue.
/**
* Return a list containing all the integers from
* both trees sorted in ascending order.
*
* Runtime: 13 ms, faster than 84.28% of Java online submissions.
* Memory Usage: 41.5 MB, less than 91.33% of Java online submissions.
*/
static List<Integer> getAllElements0(TreeNode root1, TreeNode root2) {
// **** initialization ****
List<Integer> lst = new ArrayList<>();
// **** traverse root1 adding elements to the list ****
traverse0(root1, lst);
// **** traverse root2 adding elements to the list ****
traverse0(root2, lst);
// **** sort array list ****
Collections.sort(lst);
// **** return ****
return lst;
}
We use a similar approach. This time we use an array list. Note that we sorted the array list. We could have used the merge sort last step to avoid additional sorting. I believe we could done much better if we populate the list directly from the two BSTs.
/**
* Traverse BST adding tree node values to the list.
* Recursive O(n)
*/
static void traverse0(TreeNode root, List<Integer> lst) {
if (root != null) {
// **** visit left sub tree ****
traverse0(root.left, lst);
// **** ****
lst.add(root.val);
// **** visit right sub tree ****
traverse0(root.right, lst);
}
}
This method is very similar to the previous implementation. In this case we use a list instead of a priority queue.
// **** holds elements from both binary trees ****
static List<Integer> al;
This last pass is similar. Instead of passing around the array list, we declare it static.
/**
* Return a list containing all the integers from
* both trees sorted in ascending order.
*
* Runtime: 13 ms, faster than 84.28% of Java online submissions.
* Memory Usage: 41.7 MB, less than 82.99% of Java online submission.
*/
static List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
// **** initialization ****
al = new ArrayList<>();
// **** traverse root1 adding elements to the priority queue ****
traverse(root1);
// **** traverse root2 adding elements to the priority queue ****
traverse(root2);
// **** sort the list ****
Collections.sort(al);
// **** return the list ****
return al;
}
Once again there is little to say. This is very similar to a previous implementation. The only difference is that we do not pass the array list to the traverse() method.
/**
* Traverse BST adding tree node values to the priority queue.
* Recursive O(n)
*/
static void traverse(TreeNode root) {
// **** end condition ****
if (root == null)
return;
// **** visit left sub tree ****
traverse(root.left);
// **** ****
al.add(root.val);
// **** visit right sub tree ****
traverse(root.right);
}
This method is also very similar to previous implementations. I just changed the style.
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 one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all 6,481 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.
Regards;
John
john.canessa@gmail.com