Today is Sunday. As usual I woke up at 06:00 AM and it was dark. I decided to stay in bed for a few minutes before getting up and fixing breakfast for my wife and me. The next thing was waking up around 06:45 AM. The day was clearing some, but still dark enough to require artificial light. I understand that if you fall asleep after your alarm clock goes off, that it is an indication from your body that you need additional sleep. That said; I do not recall doing much yesterday. Go figure!
As usual, for breakfast I make espresso on our Bialetti 6-cup Moka pot. Growing up my parents owned several Moka pots of different capacities. Some were used on a daily basis and others when my parents entertained family and friends. With time my mother started using a drip pot. She liked to get the first few drops and add some hot water. It was almost impossible to drink it straight up.
As I am writing this post I am reminiscing about the times that my wife have been in Italy. Italy is our best trip destination. I just did a search on Italy and coffee and the article “The Ultimate Guide to Coffee in Italy” by Agness Walewinder called my attention. Apparently the blog is about backpacking. I missed such opportunities when I was young. Our youngest son spent a month in Italy with his best friend. His friend mother had roots in Sicily and mine come from Genoa. We have traveled in Sicily and Genoa, but our favorite city in Italy is Rome. There are so many things to enjoy that the city has to offer, such as desserts, food, music, people, and sites. If you have a chance to visit Italy, do not miss Rome (or Roma as it is called by Italians). Remember the saying “When in Rome, do as the Romans do”.
Getting back to coffee, for breakfast my wife and I have a cup Cappuccino (or latte) made with hot milk and three cups of espresso each. That holds us until around mid morning. At that time I prepare what might be called an Americano or Caffé Lungo. In a nutshell is espresso with hot water to make it weaker. That said; I use three cups of espresso in each drink.
If you are interested in learning more about how coffee in Italy (I would rather say in Rome, Italy) take a gander to the post by Agness Walewinder previously mentioned. Enjoy!
Over the weekend I read an article in the Washington Post in which China `vows` a peaceful `unification` with Taiwan. Of course that is a unilateral decision. Earlier today (Monday morning) my wife mentions that several countries are helping Taiwan build up military defenses. The intentions of China are not new. Years ago for an airline to fly from any airport in China to Taiwan, they had to put the following text following the destination (Territory of China). What is interesting to note is that airlines put the business in front of the future consequences for the people of Taiwan.
Now let’s get down to the main subject of this post.
Yesterday I decided to solve “LeetCode 156 Binary Tree Upside Down”. I believe it helps to understand the structure of a binary tree.
Given the root of a binary tree, turn the tree upside down and return the new root. You can turn a binary tree upside down with the following steps: o The original left child becomes the new root. o The original root becomes the new right child. o The original right child becomes the new left child. Constraints: o The number of nodes in the tree will be in the range [0, 10]. o 1 <= Node.val <= 10 o Every right node in the tree has a sibling (a left node that shares the same parent). o Every right node in the tree has no children.
You are asked to turn a binary tree upside down. Not sure if the description and the name are appropriate. To check I used OneLook.com which took me to the Cambridge Dictionary. The definition: “having the part that is usually at the top turned to be at the bottom” seems to make sense but that does not match the requirements of the problem. I would assume that you would rotate the binary tree 180 degrees by displaying the lower levels first, finishing with level one. That does not seem to be the case with the diagram provided by LeetCode in the requirements.
For this problem we need to understand what the steps are as described in the requirements. I took a pen and paper and experimented how I would get this done. Go ahead and give it a try. I will wait for you …
… OK, you are back. It seems that we need to traverse the leftmost side of the binary tree. After we reach the leftmost node, we can apply some changes. After returning from the next recursive call (if any), we need to take care of the next level up.
I will attempt to solve the problem using Java and the VSCode IDE on a Windows computer. Feel free to use the on-line IDE provided by LeetCode.
/**
* 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 upsideDownBinaryTree(TreeNode root) {
}
}
Since we are dealing with a binary tree we need to use the description provided by LeetCode. Since LeetCode uses this definition in most binary tree problems, I have a separate file with a modified version of the class. Please ignore additional fields in the TreeNode definition since they are not used in this problem.
In addition, I have a second file in which I experiment with binary trees. Such code is not required, but I decided to use it to display the in-order traversal of the binary trees. If you wish you can write your own function; otherwise you may skip it because such code IS NOT PART OF THE SOLUTION!
The signature for the function of interest receives as an argument the root of the binary tree and returns the modified binary tree. Note that we will be altering the original binary tree within the function of interest.
1,2,3 main <<< arr: [1, 2, 3] main <<< bt inOrder: 2 1 3 upsideDownBinaryTree <<< root: (1) upsideDownBinaryTree <<< root.left: (2) upsideDownBinaryTree <<< root.right: (3) main <<< udt inOrder: 3 2 1 1,2,3,4,5 main <<< arr: [1, 2, 3, 4, 5] main <<< bt inOrder: 4 2 5 1 3 upsideDownBinaryTree <<< root: (2) upsideDownBinaryTree <<< root.left: (4) upsideDownBinaryTree <<< root.right: (5) upsideDownBinaryTree <<< root: (1) upsideDownBinaryTree <<< root.left: (2) upsideDownBinaryTree <<< root.right: (3) main <<< udt inOrder: 5 4 3 2 1 1 main <<< arr: [1] main <<< bt inOrder: 1 main <<< udt inOrder: 1 main <<< arr: null main <<< bt inOrder: main <<< udt inOrder: 1,2,3,4,5,6,7 main <<< arr: [1, 2, 3, 4, 5, 6, 7] main <<< bt inOrder: 4 2 5 1 6 3 7 upsideDownBinaryTree <<< root: (1) upsideDownBinaryTree <<< root: (2) upsideDownBinaryTree <<< left: (4) upsideDownBinaryTree <<< left: (4) main <<< udt inOrder: 5 4 6 3 7 2 1
The input line holds a list of integers that are associated with the nodes in the binary tree. The description of the input line matches a level tree traversal from top to bottom. We have seen this in most LeetCode problems regarding binary trees.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** initialization ****
Integer[] arr = null;
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read the input line ****
String inputLine = br.readLine().trim();
// **** read and populate array of Integers (if possible) ****
if (!inputLine.equals(""))
arr = Arrays.stream(inputLine.split(","))
.map(Integer::parseInt)
.toArray(Integer[]::new);
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** create and populate the binary tree ****
BST bt = new BST();
bt.root = bt.populate(arr);
// ???? ????
System.out.println("main <<< bt inOrder: " + bt.inOrder(bt.root));
// **** call function of interest ****
TreeNode newRoot = upsideDownBinaryTree(bt.root);
// // **** create and populate the binary tree (example 1) ****
// TreeNode root = new TreeNode(1);
// root.left = new TreeNode(2);
// root.right = new TreeNode(3);
// root.left.left = new TreeNode(4);
// root.left.right = new TreeNode(5);
// // **** call function of interest ****
// TreeNode newRoot = upsideDownBinaryTree(root);
// **** create an empty upside down binary tree ****
BST udt = new BST();
// **** assign the root to the upside down binary tree ****
udt.root = newRoot;
// ???? ????
System.out.println("main <<< udt inOrder: " + udt.inOrder(udt.root));
}
In our test scaffold we use the BST.populate() method. This class or method is NOT PART OF THE SOLUTION. You could as easily create the binary tree by hand. If you have trouble doing so, leave me a message and I will update this post. I went back to the code and updated the test scaffold. We will discuss generating the binary tree by hand when we look at the code next.
In our test scaffold we are able to read the input line and generate an Integer[] array with the values for the binary tree nodes. The order is specified in a depth level first traversal starting with the root node. LeetCode tends to describe binary trees in this fashion. Note that our code will not be able to handle `null` nodes. In this case, we will not deal with such condition. We have done so in previous posts.
We create a binary tree and populate it with the contents of the Integer[] arr array. Note that the BST class IS NOT PART OF THE SOLUTION! As we mentioned before, we can construct the test cases manually. The instructions for building the binary tree for test case 1 have been commented out. If you wish to test such code, just comment out the code that we use to read in the input line and the use of the BST class. You will also like to comment out the last few lines in the test code since they also refer to the BST class.
OK, one way or the other we created a binary tree and call the function of interest.
/**
* Given the root of a binary tree,
* turn the tree upside down and
* return the new root.
* Recursive call.
*
* 145 / 145 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 39.2 MB
*/
static public TreeNode upsideDownBinaryTree(TreeNode root) {
// **** base case ****
if (root == null || root.left == null) return root;
// **** process left children (recursive call) ****
TreeNode left = upsideDownBinaryTree(root.left);
// ???? ????
System.out.println("upsideDownBinaryTree <<< root: " + root.toString());
System.out.println("upsideDownBinaryTree <<< root.left: " + root.left.toString());
System.out.println("upsideDownBinaryTree <<< root.right: " + root.right.toString());
// **** set new root left child ****
root.left.left = root.right;
// **** set new root right child ****
root.left.right = root;
// **** clear root children (have been repositioned) ****
root.left = null;
root.right = null;
// **** new root ****
return left;
}
I initially created a skeleton of a binary tree in-order traversal function and experimented with it. At some point I deleted since there was no need to perform the full tree traversal. We just need to call the function of interest recursively and when the function returns take care of the modifications to the tree. Note that in this case we are not creating a separate binary tree; we are just modifying the current one.
We start with the base case. We then process the current node. It starts by processing the root of the binary tree. Note that the recursive call descends on the leftmost path until it hits the last node. At that point we are ready to start making the changes to each level from the bottom to the top of the tree.
I have left some statements to allow us to track the operations. Such statements must be deleted if you wish to submit the code to verify its operation.
We perform the steps suggested by the requirements. Note that the descriptions and order of all statements does not match exactly to the requirements. I guess LeetCode was not going to spell exactly what the solution entails. The clearing of the root children nodes is required and unless I missed something, it was not specified in the requirements.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different web sites (i.e., HackerRank, LeetCode).
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. 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.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John