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:
[1, 200].[0, 200].The key idea in Leaf-Similar Trees is to compare the sequence of leaf nodes from two binary trees. A leaf node is defined as a node with no left or right child. The problem becomes easier if we think of it as generating the leaf value sequence for each tree and then checking whether the two sequences are identical.
A common strategy is to use Depth-First Search (DFS). Traverse each tree recursively and collect values only when a node has node.left == null and node.right == null. Store these values in an ordered structure such as a list. Since DFS naturally explores the entire tree, it ensures every leaf is visited in left-to-right order.
After generating both sequences, simply compare them. If they match exactly, the trees are leaf-similar. The traversal touches each node once, giving a time complexity of O(n + m), where n and m are the sizes of the two trees. The extra space used mainly comes from recursion and storing leaf sequences.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS traversal to collect leaf sequences and compare | O(n + m) | O(n + m) |
NeetCodeIO
This approach involves using a recursive depth-first search (DFS) to traverse each binary tree and collect the leaf node values by diving into each sub-tree starting from the root node. We store the values of all leaf nodes from left to right in a list. After extracting the sequences from both trees, we compare these sequences to determine if the trees are leaf-similar.
Time Complexity: O(N) where N is the number of nodes in the tree, as we need to visit each node.
Space Complexity: O(H) where H is the height of the tree, due to the recursive stack.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:
9 def dfs(node):
10 if not node:
11 return []
12 if not node.left and not node.right:
13 return [node.val]
14 return dfs(node.left) + dfs(node.right)
15
16 return dfs(root1) == dfs(root2)We define a nested function dfs inside our main function to recursively traverse the binary tree. The dfs function returns a list of leaf node values by first checking if a node is null (in which case it returns an empty list), then it checks if the node is a leaf node (no left and right children), and if so, it returns a list containing the node's value. Otherwise, it recursively calls itself on the left and right children and concatenates their results. Lastly, we compare the two leaf sequences to decide if the trees are leaf-similar.
This method employs an iterative version of depth-first search utilizing a stack to collect leaves of the tree. By substituting recursion with a stack, we manually handle tree traversal, but the core logic remains similar: traverse each tree, collect leaves, and compare leaf sequences.
Time Complexity: O(N), with N as the number of nodes in the tree, because every node is visited.
Space Complexity: O(H), where H is the height of the tree. This space is used by the stack during DFS traversal.
1import java.util.Stack;
2
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
DFS explores each branch fully before moving to the next, making it easy to detect leaf nodes during traversal. By recording leaf values when both children are null, we can naturally build the leaf sequence in the correct order.
Yes, variations of binary tree traversal problems are common in FAANG-style interviews. While this specific problem is labeled easy, it tests understanding of DFS, recursion, and tree traversal patterns that frequently appear in technical interviews.
The optimal approach uses Depth-First Search (DFS) to collect the leaf node values from both trees in left-to-right order. After generating these sequences, compare them directly. If the sequences match, the trees are considered leaf-similar.
A simple list or array works well to store the leaf values encountered during DFS traversal. The order of insertion matters because the problem requires comparing the exact sequence of leaves between two trees.
Here, a Stack is used for both implementing the DFS traversal and collecting leaf node values iteratively. For leaf nodes, their values are added to a separate stack (list) leaves. By performing this for both root1 and root2, we get their leaf sequences, which are compared for equality at the end.