Good morning gals and guys! Hope you day has started on the right note. Today in the Twin Cities of Minneapolis and St. Paul we are expecting a high temperature of 67F and the day is sunny. Starting today the two-week forecast shows high temperatures in the upper 60’s to mid to lower 70’s. All looks nice, but we are somewhat low on precipitation. From my backyard I can see a small pond with very low water levels. Hopefully farmers are receiving enough rain to have a good crop this fall.
This morning I watched a session from AWS Summit Online. The session is named “Amazon DynamoDB: Untold stories of databases in a serverless world” by Angela Timofte. She is a data platform manager with Trustpilot. What called my attention were a set of points she brought up which illustrates how important is to allow your technical staff to experiment, learn and make mistakes. Such approach has helped the company move from MySQL to MongoDB and currently to DynamoDB. What is more important, the company currently uses about ten different database engines to store different types of data. They are using the right tools for the jobs (one size does not fit all). If you get a chance take a look at the 22 minute presentation here.
Now let’s get to the main subject of this post.
I decided to work on LeetCode 101 Symmetric Tree.
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center). Constraints: o The number of nodes in the tree is in the range [1, 1000]. o -100 <= Node.val <= 100 Related Topics: * Tree o Depth-First Search * Breadth-first Search
The problem definition is simple. Given the root of a binary tree we have to determine if the tree is symmetric. In other words, if we draw a vertical line through the root node which splits the binary tree into two halves, would the two sides be mirrored or not?
LeetCode suggest two possible approaches using DFS and BFS.
We will solve this problem using the Java programming language and the VSCode IDE on a Windows 10 computer. You could use a different operating system (i.e., Linux) and the same tools. If you want to make your life easy, just solve the problem on 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 boolean isSymmetric(TreeNode root) {
}
}
The signature of the method makes sense. We are given a binary tree using the TreeNode class. We have used this class many times in this post.
1
/ \
2 2
/ \ / \
3 4 4 3
1,2,2,3,4,4,3
main <<< arr: [1, 2, 2, 3, 4, 4, 3]
main <<< output: true
main <<< output: true
1
/ \
2 2
\ \
3 3
1,2,2,null,3,null,3
main <<< arr: [1, 2, 2, null, 3, null, 3]
main <<< output: false
main <<< output: false
1
/ \
2 2
/ /
2 2
1,2,2,2,null,2
main <<< arr: [1, 2, 2, 2, null, 2]
main <<< output: false
main <<< output: false
1
/ \
2 2
\ /
3 3
1,2,2,null,3,3
main <<< arr: [1, 2, 2, null, 3, 3]
main <<< output: true
main <<< output: true
The first two cases are examples provided by LeetCode. The other two also came from LeetCode when a couple of my submissions failed.
For visualization purposes I drew the associated binary tree representations. The input for each test case is a line of integers separated by ‘,’s.
Looking at the first example we can see that if we draw a vertical line through the root node the tree is symmetric.
If you do the same with the second example, the tree is NOT symmetric.
Our test code which you will not have to implement therefore is NOT PART OF THE SOLUTION, appears to read the input line and generate a Integer[]. With that Integer[] array we must be able to create and populate the binary tree for each test case.
The test code seems to have two implementations. As we will shortly find out, the first is recursive and the second iterative.
/**
* Test scaffold
* @throws IOException
*
* NOT PART OF SOLUTION
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new java.io.InputStreamReader(System.in));
// **** create String[] with values for the BST ****
String[] strArr = br.readLine().trim().split(",");
// **** close the buffered reader ****
br.close();
// ???? ????
// System.out.println("main <<< strArr.length: " + strArr.length);
// System.out.println("main <<< strArr: " + Arrays.toString(strArr));
// **** generate an Integer[] to build the BST ****
Integer[] arr = new Integer[strArr.length];
for (int i = 0; i < strArr.length; i++) {
if (strArr[i].equals("null") || strArr[i].isEmpty())
arr[i] = null;
else
arr[i] = Integer.parseInt(strArr[i]);
}
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** create and populate the BT ****
BST bst = new BST();
bst.root = bst.populate(arr);
// ???? ????
// System.out.println("main <<< DFS: " + bst.inOrder(bst.root));
// System.out.println("main <<< BFS: " + bst.levelOrder());
// **** determine if BT is or is NOT symmetric ****
System.out.println("main <<< output: " + isSymmetricR(bst.root));
// **** determine if BT is or is NOT symmetric ****
System.out.println("main <<< output: " + isSymmetricI(bst.root));
}
Not much to add at this time. Our test code reads the input line and generates an Integer[] array. We generate the associated binary tree.
We have commented out a couple lines which display the tree using a depth first search and a breadth first search approaches.
Now that we have a good visualization of the problem, we implement a recursive and then an iterative approach.
/**
* Given the root of a binary tree,
* check whether it is a mirror of itself.
* Entry point for recursive call.
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 36.9 MB, less than 63.58% of Java online submissions.
*/
static boolean isSymmetricR(TreeNode root) {
return isSymmetricR(root.left, root.right);
}
The recursive entry point is simple. We start at the root and wish to determine if the subsequent nodes are symmetric or not. We pass the left and right sub trees to a recursive call. So far this seems to be reasonable. The tricky part is in the recursive call.
/**
* Given the root of a binary tree,
* check whether it is a mirror of itself.
* Recursive call.
*/
static private boolean isSymmetricR(TreeNode left, TreeNode right) {
// **** base case(es) ****
if (left == null || right == null)
return left == right;
if (left.val != right.val)
return false;
// **** recurse ****
return isSymmetricR(left.left, right.right) &&
isSymmetricR(left.right, right.left);
}
We first define our base case. If both nodes are null we return true but if one node is null and the other is not we return false. Now we check if the values of the nodes are different and return false.
The tricky part is the recursive call. We need to check the proper nodes. Please take a mush time as you need to see how the test is performed. I will wait … OK, you are back so we may proceed.
/**
* Given the root of a binary tree,
* check whether it is a mirror of itself.
* Iterative approach using BFS.
*
* Runtime: 1 ms, faster than 22.70% of Java online submissions.
* Memory Usage: 38.5 MB, less than 8.37% of Java online submissions.
*/
static boolean isSymmetricI(TreeNode root) {
// **** initialization ****
Queue<TreeNode> q = new LinkedList<>();
// **** prime the queue ****
q.add(root);
q.add(root);
// **** loop while we have nodes in the queue ****
while (!q.isEmpty()) {
// ???? ????
System.out.println("<<< q: " + q.toString());
// **** retrieve and remove head nodes from the queue ****
TreeNode t1 = q.poll();
TreeNode t2 = q.poll();
// ???? ????
System.out.println("<<< t1: " + t1 + " ? t2: " + t2);
// **** both nodes are null (move to next pair of nodes) ****
if (t1 == null && t2 == null)
continue;
// **** one of nodes is null (tree not symmetric) ****
if (t1 == null || t2 == null)
return false;
// **** node values are different (tree not symmetric) ****
if (t1.val != t2.val)
return false;
// **** the right and left children of the two nodes
// are inserted in the queue in opposite order ****
q.add(t1.left);
q.add(t2.right);
q.add(t1.right);
q.add(t2.left);
}
// **** tree is symmetric ****
return true;
}
This method uses an iterative approach to the problem. Note that it uses a modified BFS approach which we have used to solve different problems i.e., Print a Binary Tree in Vertical Order. Look for the bfs() method.
We start by initializing a queue. We then prime the queue.
The loop that follows continues until the queue is empty. Compare this code with the bfs() in the previously mentioned post.
In the loop we take out the next couple nodes. We need to do so because we want to compare the corresponding nodes from the left and right sub trees starting at the root.
After a set of checks we insert into the queue the proper nodes from the left and right sub trees. This requires some thought and understanding. Please take your time to make sure this is clear. Will wait… OK, let’s move on.
If we complete the tree traversal, the tree is symmetric so we return true.
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, 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