In this post we will be solving LeetCode 872. Leaf-Similar Trees. As usual, if interested, please visit the LeetCode site and read the current version of the problem to make sure all is well before you start developing code.
Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence. Two binary trees are considered leaf-similar if their leaf value sequence is the same. Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar. Constraints: o The number of nodes in each tree will be in the range [1, 200]. o Both of the given trees will have values in the range [0, 200]. Related Topics: o Tree o Depth-First Search o Binary Tree
We are given two binary trees. We need to determine if the sequence of leaf nodes match or not. Seems like an in-order tree traversal problem. We could populate a list with the leaf nodes of the first tree and repeat with the nodes of the second tree. Our answer will be based on the contents of both lists.
We will be developing the solution using the Java programming language and the VSCode IDE on a Windows platform. It is simpler to solve the problem using the on-line IDE provided by LeetCode. Since I am solving the problem on my Windows computer, I will have to build a simple test scaffold to read the input data for the two binary trees, create and populate the binary trees, call the function of interest and display the results. 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 boolean leafSimilar(TreeNode root1, TreeNode root2) {
}
}
The signature for the function of interest matches pretty well the requirements.
Note that we are also given the documentation for the TreeNode class. Once again, since I am solving the problem in my Windows computer I will have to implement the TreeNode class. Note that implementing the TreeNode class IS NOT PART OF THE SOLUTION!
3,5,1,6,2,9,8,null,null,7,4 3,5,1,6,7,4,2,null,null,null,null,null,null,9,8 main <<< strArr1: [3, 5, 1, 6, 2, 9, 8, null, null, 7, 4] main <<< strArr2: [3, 5, 1, 6, 7, 4, 2, null, null, null, null, null, null, 9, 8] main <<< arr1: [3, 5, 1, 6, 2, 9, 8, null, null, 7, 4] main <<< arr2: [3, 5, 1, 6, 7, 4, 2, null, null, null, null, null, null, 9, 8] main <<< bt1.inOrder: 6 5 7 2 4 3 9 1 8 main <<< bt1.preOrder: 3 5 6 2 7 4 1 9 8 main <<< bst.levelOrderTraversal: [[3], [5, 1], [6, 2, 9, 8], [7, 4]] main <<< bt2.inOrder: 6 5 7 3 4 1 9 2 8 main <<< bt2.preOrder: 3 5 6 7 1 4 2 9 8 main <<< bst.levelOrderTraversal: [[3], [5, 1], [6, 7, 4, 2], [9, 8]] main <<< leafSimilar0: true main <<< leafSimilar: true 1,2,3 1,3,2 main <<< strArr1: [1, 2, 3] main <<< strArr2: [1, 3, 2] main <<< arr1: [1, 2, 3] main <<< arr2: [1, 3, 2] main <<< bt1.inOrder: 2 1 3 main <<< bt1.preOrder: 1 2 3 main <<< bst.levelOrderTraversal: [[1], [2, 3]] main <<< bt2.inOrder: 3 1 2 main <<< bt2.preOrder: 1 3 2 main <<< bst.levelOrderTraversal: [[1], [3, 2]] main <<< leafSimilar0: false main <<< leafSimilar: false
The first two lines of each test case provide the description of the input binary trees.
The test code seems to be displaying intermediate variables and data structures that are used to generate the two binary trees used as arguments for the function of interest. This is done with the purpose of being able to verify that all is well before we call the function of interest. I like to follow a Test Driven Development approach when developing software.
Note that our test scaffold appears to be calling two implementations of the function of interest. Both are similar but the second seems to run faster than the first. We will see this when we visit the implementations.
/**
* Test scaffold.
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** create String[] with values for the first BST ****
String[] strArr1 = br.readLine().trim().split(",");
// **** create String[] with values for the second BST ****
String[] strArr2 = br.readLine().trim().split(",");
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< strArr1: " + Arrays.toString(strArr1));
System.out.println("main <<< strArr2: " + Arrays.toString(strArr2));
// **** generate an Integer[] to build the first BT ****
Integer[] arr1 = new Integer[strArr1.length];
for (int i = 0; i < strArr1.length; i++) {
if (strArr1[i].equals("null") || strArr1[i].isEmpty())
arr1[i] = null;
else
arr1[i] = Integer.parseInt(strArr1[i]);
}
// **** generate an Integer[] to build the second BT ****
Integer[] arr2 = new Integer[strArr2.length];
for (int i = 0; i < strArr2.length; i++) {
if (strArr2[i].equals("null") || strArr2[i].isEmpty())
arr2[i] = null;
else
arr2[i] = Integer.parseInt(strArr2[i]);
}
// ???? ????
System.out.println("main <<< arr1: " + Arrays.toString(arr1));
System.out.println("main <<< arr2: " + Arrays.toString(arr2));
// **** create and populate the first BT ****
BST bt1 = new BST();
bt1.root = bt1.populate(arr1);
// ???? ????
System.out.println("main <<< bt1.inOrder: " + bt1.inOrder(bt1.root));
System.out.println("main <<< bt1.preOrder: " + bt1.preOrder(bt1.root));
// ???? ????
System.out.print("main <<< bst.levelOrderTraversal: ");
System.out.println(bt1.levelOrderTraversal(bt1.root).toString());
// **** create and populate the second BT ****
BST bt2 = new BST();
bt2.root = bt2.populate(arr2);
// ???? ????
System.out.println("main <<< bt2.inOrder: " + bt2.inOrder(bt2.root));
System.out.println("main <<< bt2.preOrder: " + bt2.preOrder(bt2.root));
// ???? ????
System.out.print("main <<< bst.levelOrderTraversal: ");
System.out.println(bt2.levelOrderTraversal(bt2.root).toString());
// **** call the function of interest and display result ****
System.out.println("main <<< leafSimilar0: " + leafSimilar0(bt1.root, bt2.root));
// **** call the function of interest and display result ****
System.out.println("main <<< leafSimilar: " + leafSimilar(bt1.root, bt2.root));
}
The test code reads the two input lines and populates a couple of arrays for each binary tree.
The binary trees are created, populated and displayed in different ways in order to verify that all is well before we call the function of interest. Such code is in my GitHub repository but IT IS NOT PART OF THE SOLUTION!
The code then calls the two implementations of the function of interest and displays the results which seem to be the same and match the results for the test cases provided by LeetCode.
// **** list used by leafSimilar0 ****
static List<Integer> lst = null;
/**
* Return true if and only if the two given trees
* with head nodes root1 and root2 are leaf-similar.
*
* Execution: O(N) - Space: O(N)
*
* 40 / 40 test cases passed.
* Status: Accepted
* Runtime: 8 ms
* Memory Usage: 38.9 MB
*/
static public boolean leafSimilar0(TreeNode root1, TreeNode root2) {
// **** initialization ****
List<Integer> lst1 = null;
List<Integer> lst2 = null;
// **** in-order first BT traversal ****
lst = new ArrayList<Integer>();
leafSimilar(root1);
lst1 = lst;
// **** in-order second BT traversal ****
lst = new ArrayList<Integer>();
leafSimilar(root2);
lst2 = lst;
// ???? ????
// System.out.println("<<< lst1: " + lst1.toString());
// System.out.println("<<< lst2: " + lst2.toString());
// **** compare lists ****
return lst1.equals(lst2);
}
In this implementation we declare a static reference to a list that will be used to collect two lists which will be compared to determine the result.
The function of interest defines two lists.
It starts by declaring a list associated with the static `lst`. An auxiliary recursive function `leafSimilar` is called with the root of the first binary tree. The populated `lst` is referenced by the `lst1` variable.
The process repeats for the second binary tree.
The final step is to compare if both lists contain nodes with the same values in the same order.
/**
* In-order traversal collecting leaf nodes.
* Recursive function.
*/
static private void leafSimilar(TreeNode root) {
// **** base case ****
if (root == null) return;
// **** visit left child ****
leafSimilar(root.left);
// **** check if leaf node ****
if (root.left == null && root.right == null)
lst.add(root.val);
// **** visit right child ****
leafSimilar(root.right);
}
This is a recursive function that mimics an in-order three traversal. Of interest is when we visit the current node. If both children are null this means we are visiting a leaf node. We stash the value of the current node in the global `lst` list.
Let’s take a look at the comments section of the implementation of the function of interest. The function was accepted by LeetCode, but the execution time is not that great. Perhaps we can do better!
/**
* Return true if and only if the two given trees
* with head nodes root1 and root2 are leaf-similar.
*
* Execution: O(N) - Space: O(n)
*
* 40 / 40 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 39.1 MB
*/
@SuppressWarnings("unchecked")
static public boolean leafSimilar(TreeNode root1, TreeNode root2) {
// **** initialization ****
List<Integer> lst1 = new ArrayList<Integer>();
List<Integer> lst2 = new ArrayList<Integer>();
// **** in-order first BT traversal ****
List<Integer>[] arr1 = new ArrayList[1];
arr1[0] = lst1;
leafSimilar(root1, arr1);
// **** in-order second BT traversal ****
List<Integer>[] arr2 = new ArrayList[1];
arr2[0] = lst2;
leafSimilar(root2, arr2);
// ???? ????
// System.out.println("<<< lst1: " + lst1.toString());
// System.out.println("<<< lst2: " + lst2.toString());
// **** compare lists ****
return lst1.equals(lst2);
}
This implementation of the function of interest does not make use of a static variable for the list.
Note the annotation before the function declaration. We are going to declare simple arrays of ArrayList which is not the norm when you use a Java generic. You can read more here.
It starts by declaring two lists.
We declare an array of one element `arr1` and put the reference to `lst1` in it. We then call the recursive auxiliary function `leafSimilar` to populate the list with the leaf nodes.
The process repeats for the second binary tree.
As in the previous implementation of the function of interest, the last step is to compare the contents of both lists.
/**
* In-order traversal collecting leaf nodes.
* Recursive function.
*/
static private void leafSimilar(TreeNode root, List<Integer>[] lst) {
// **** base case ****
if (root == null) return;
// **** visit left child ****
leafSimilar(root.left, lst);
// **** check if leaf node ****
if (root.left == null && root.right == null)
lst[0].add(root.val);
// **** visit right child ****
leafSimilar(root.right, lst);
}
The `leafSimilar` recursive auxiliary function is modeled as an in-order binary tree traversal. I guess there is no more to add since the behavior is very similar to the previous recursive auxiliary function.
Now let’s get back to the comments section of the function of interest implementation. It seems that it is faster than the previous one!
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named LeafSimilarTrees.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
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 / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John