{x}
blog image

Leaf-Similar Trees

Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

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.

 

Example 1:

Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Output: true

Example 2:

Input: root1 = [1,2,3], root2 = [1,3,2]
Output: false

 

Constraints:

  • The number of nodes in each tree will be in the range [1, 200].
  • Both of the given trees will have values in the range [0, 200].

Solution Explanation: Leaf-Similar Trees

The problem asks to determine if two binary trees are "leaf-similar". Two trees are leaf-similar if their leaf nodes, when read from left to right, produce the same sequence of values.

The most efficient approach involves a Depth-First Search (DFS) traversal of both trees. The DFS function will recursively explore each tree and collect the values of the leaf nodes in separate lists. Finally, it compares these lists for equality.

Algorithm:

  1. DFS Function: A recursive function dfs is defined. This function takes a tree node and a list as input. It works as follows:

    • Base Case: If the current node is a leaf node (i.e., it has no children), its value is appended to the input list.
    • Recursive Step: If the node is not a leaf node, the dfs function is recursively called on its left and right children (if they exist).

  2. Main Function:

    • Two empty lists, l1 and l2, are created to store the leaf values of root1 and root2, respectively.
    • The dfs function is called on root1 and root2 with their corresponding lists.
    • Finally, the function compares l1 and l2 for equality using l1 == l2 (Python) or l1.equals(l2) (Java). If they are equal, the trees are leaf-similar, and the function returns true; otherwise, it returns false.

Time and Space Complexity:

  • Time Complexity: O(N), where N is the total number of nodes in both trees. This is because the DFS function visits each node exactly once.
  • Space Complexity: O(N) in the worst case. This is due to the recursive call stack during DFS (which can be as deep as the height of the tree) and the space used to store the lists of leaf node values. In the best-case scenario (balanced trees), the space complexity would be O(log N).

Code Examples (Python, Java, C++, Go, Rust, JavaScript):

The provided code examples in multiple languages implement this algorithm. They all follow the same structure: a dfs function for the traversal and a main function to orchestrate the comparison. The specific syntax varies slightly between languages, but the core logic remains consistent. Note that the tree node definitions are provided as comments in some code snippets as they are typically predefined in the leetcode environment.

The crucial parts are the recursive dfs function which extracts the leaf node values and the final comparison of lists. These examples demonstrate the practical implementation of the algorithm described above.