It is past 06:00 PM CST in the Twin Cities of Minneapolis and St. Paul. I am quite tired and it is only Tuesday. Hope your week is going smoother than mine.
Earlier in the day I read the article “Let’s Not Dumb Down the History of Computer Science” by Donald E. Knuth, Len Shustek in Communications of the ACM, February 2021, Vol. 64 No. 2, Pages 33-35. If you have trouble accessing the article then you should be able to watch “Stanford Lecture: 2014 Kailath Lecture: Stanford Professor Donald Knuth” on YouTube.
In a nutshell Donald Knuth expresses the need for Computer Science history to be documented. Philosophically speaking I believe he is right on the point.
I decided to tackle LeetCode 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree.
Given two binary trees original and cloned and given a reference to a node target in the original tree. The cloned tree is a copy of the original tree. Return a reference to the same node in the cloned tree. Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree. Constraints: o The number of nodes in the tree is in the range [1, 10^4]. o The values of the nodes of the tree are unique. o target node is a node from the original tree and is not null. Follow up: Solve the problem if repeated values on the tree are allowed.
We are given two binary trees. One is the original and the second cloned from the first. We are also given the target node from the original binary tree and we are supposed to find the node with the same value in the cloned tree. It looks like this is a depth first traversal problem.
public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
}
The signature for the method we need to implement appears to match the requirements for the problem.
I will solve this problem using the Java programming language on a Windows 10 machine using the VSCode IDE. It would probably make sense if you solve the problem directly on the LeetCode site using the provided IDE. If you do so there will be no need to implement a test scaffolding and all the associated methods needed to manipulate the binary tree.
7,4,3,null,null,6,19 3 main <<< strArr: [7, 4, 3, null, null, 6, 19] main <<< arr: [7, 4, 3, null, null, 6, 19] main <<< targetVal: 3 main <<< original levelOrder: 7 4,3 6,19 main <<< cloned levelOrder: 7 4,3 6,19 main <<< target: (3) main <<< getTargetCopy1: (3) main <<< getTargetCopy: (3) 7 7 main <<< strArr: [7] main <<< arr: [7] main <<< targetVal: 7 main <<< original levelOrder: 7 main <<< cloned levelOrder: 7 main <<< target: (7) main <<< getTargetCopy1: (7) main <<< getTargetCopy: (7) 8,null,6,null,5,null,4,null,3,null,2,null,1 4 main <<< strArr: [8, null, 6, null, 5, null, 4, null, 3, null, 2, null, 1] main <<< arr: [8, null, 6, null, 5, null, 4, null, 3, null, 2, null, 1] main <<< targetVal: 4 main <<< original levelOrder: 8 6 5 4 3 2 1 main <<< cloned levelOrder: 8 6 5 4 3 2 1 main <<< target: (4) main <<< getTargetCopy1: (4) main <<< getTargetCopy: (4) 1,2,3,4,5,6,7,8,9,10 5 main <<< strArr: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] main <<< arr: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] main <<< targetVal: 5 main <<< original levelOrder: 1 2,3 4,5,6,7 8,9,10 main <<< cloned levelOrder: 1 2,3 4,5,6,7 8,9,10 main <<< target: (5) main <<< getTargetCopy1: (5) main <<< getTargetCopy: (5) 1,2,null,3 2 main <<< strArr: [1, 2, null, 3] main <<< arr: [1, 2, null, 3] main <<< targetVal: 2 main <<< original levelOrder: 1 2 3 main <<< cloned levelOrder: 1 2 3 main <<< target: (2) main <<< getTargetCopy1: (2) main <<< getTargetCopy: (2)
We are provided two lines of input. The first is the depth first traversal of the original binary tree and the second lien holds the value for the target node.
Our test scaffolding appear to display the contents of a String[] that holds the values for the binary tree. It the displays an Integer[] with the values now in binary. The value for the target node is read and displayed.
It seems that our test code creates and populates the original binary tree. The binary tree is then displayed.
The operation repeats but this time we deal creating and populating the cloned binary tree.
The test scaffolding appears to have located and displayed the target node in the original tree. At this point we have the three arguments to implement the method of interest.
The next two lines in each test case seem to display the target node from the cloned tree. Apparently we have two implementations that seem to produce the same results.
/**
* Test scaffolding
* !!!! NOT PART OF THE SOLUTION !!!!
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read tree node values into a Integer[] (does not allow null values) ****
// Integer[] arr = Stream.of(br.readLine().trim().split(","))
// .mapToInt(Integer::parseInt)
// .boxed()
// .toArray(Integer[]::new);
// **** read tree node values into a String[] (allows null values) ****
String[] strArr = br.readLine().trim().split(",");
// **** read traget node value ****
int targetVal = Integer.parseInt(br.readLine().trim());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< strArr: " + Arrays.toString(strArr));
// **** create and populate Integer[] ****
Integer[] arr = new Integer[strArr.length];
for (int i = 0; i < strArr.length; i++) {
if (strArr[i].equals("null") == false)
arr[i] = Integer.parseInt(strArr[i]);
else
arr[i] = null;
}
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
System.out.println("main <<< targetVal: " + targetVal);
// **** create and populate a original binary tree ****
BST original = new BST();
original.root = original.populate(arr);
// ???? ????
System.out.println("main <<< original levelOrder:");
System.out.println(original.levelOrder());
// **** create and clone the original binary tree ****
BST cloned = new BST();
cloned.root = cloned.cloneTree(original.root);
// ???? ????
System.out.println("main <<< cloned levelOrder:");
System.out.println(cloned.levelOrder());
// **** get node with the specified value ****
TreeNode target = original.findBT(original.root, targetVal);
if (target != null)
System.out.println("main <<< target: " + target.toString());
else {
System.out.println("main <<< target: null");
System.exit(-1);
}
// **** get the target node from the clonned tree ****
TreeNode node = getTargetCopy1(original.root, cloned.root, target);
System.out.println("main <<< getTargetCopy1: " + node.toString());
// **** get the target node from the clonned tree ****
node = getTargetCopy(original.root, cloned.root, target);
System.out.println("main <<< getTargetCopy: " + node.toString());
}
The test scaffolding IS NOT PART OF THE SOLUTION! If you solve the problem in your computer you will need a test scaffolding. Please feel free to use the one I had to generate. When satisfied with the results, you will need to copy the code for the solution to the LeetCode website and give it a try.
The test code uses a buffered reader to read the input lines. One the arr[] is available we use it to populate a binary tree. To check if things are working as expected, we perform a level order traversal and display the results.
Now we need to generate a clone of the original binary tree. This IS NOT PART OF THE SOLUTION either! We create a binary tree and then populate it cloning the original binary tree. Ad this point we display the contents of the cloned binary tree. I will not cover the code for the cloneTree method here. You can find it and a lot more in the BST.java file in the GitHub repository associated with this post.
At this point in time we have generated the original and cloned binary trees. We now need to get a reference to the target node in the original binary tree. We use the findBT method to get such reference. The code for that method can also be found in the BST.java source code file.
We now invoke a version of the method of interest and display the result. The process repeats with a different implementation. Both values match and also match the value of the target node. So far, things appear to be working well.
/**
* Return a reference to the same node in the cloned tree.
*
* Runtime: 2 ms, faster than 58.89% of Java online submissions.
* Memory Usage: 113.4 MB, less than 12.23% of Java online submissions.
*/
static TreeNode getTargetCopy1(final TreeNode original, final TreeNode cloned, final TreeNode target) {
// **** sanity checks ****
if (cloned.val == target.val)
return cloned;
// **** initialization ****
TreeNode[] found = new TreeNode[1];
// **** look for target in the cloned tree ****
getTargetCopy1(cloned, target, found);
// **** return node ****
return found[0];
}
This method is the entry point for a recursive method with the same name but different arguments. The idea is to perform a recursive operation to locate the node that matches the target and return it to the caller. The core is in the recursive method that follows.
/**
* Return a reference to the same node in the cloned tree.
* Recursive call.
*/
static void getTargetCopy1(TreeNode root, TreeNode target, TreeNode[] found) {
if (root != null) {
// **** traverse left sub tree ****
getTargetCopy1(root.left, target, found);
// **** check if values match ****
if (root.val == target.val)
found[0] = root;
// **** traverse right sub tree ****
getTargetCopy1(root.right, target, found);
}
}
This is the associated recursive method. It implements a depth first search in order traversal of a binary tree. The idea is to locate the node in this binary tree with the value of the target node from the original binary tree. When we encounter such node, we update the found[] array.
/**
* Return a reference to the same node in the cloned tree.
* Recursive call.
*
* Runtime: 1 ms, faster than 96.59% of Java online submissions.
* Memory Usage: 113.4 MB, less than 12.23% of Java online submissions.
*/
static TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
// **** sanity checks ****
if (original == null || cloned.val == target.val)
return cloned;
// **** visit left sub tree ****
TreeNode node = getTargetCopy(original.left, cloned.left, target);
// **** check if we found target node ****
if (node != null)
return node;
// **** visit right sub tree ****
return getTargetCopy(original.right, cloned.right, target);
}
In this implementation we also perform a depth first search in order traversal of a binary tree, but we do use both binary trees simultaneously. We look for it on the left sub tree. If found we are done. If not we search the right sub tree and return the result.
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,302 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