Leaf-Similar Trees
Problem
Given two binary trees root1 and root2, return true if and only if their leaf value sequences are the same.
- The number of nodes in each tree is in the range [1, 200]
- 0 ≤ Node.val ≤ 200
Example
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]trueThe leaf sequence of root1 is [6,7,4,9,8]. The leaf sequence of root2 is also [6,7,4,9,8]. The algorithm performs a DFS on each tree, collecting leaf values in order. It then compares the two sequences for equality. The critical moment is when the algorithm identifies leaf nodes (nodes with no children) and appends their values to the leaf list. By comparing these sequences, the algorithm determines if the trees are leaf-similar.
Approach
Straightforward Solution
A brute-force approach might attempt to compare entire tree structures or perform multiple traversals, but this is unnecessary and inefficient since only leaf sequences matter. Extracting leaf sequences separately and then comparing them is simpler and more efficient.
Core Observation
The leaf value sequence of a binary tree is the ordered list of values of its leaf nodes, which can be extracted by a depth-first traversal that records values only when a node has no children.
Path to Optimal
PreviewThe key insight is to perform a DFS on each tree to collect leaf values in left-to-right order. This reduces the problem to comparing two lists of integers…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewDefine a helper DFS function that traverses a tree recursively, appending node values to a list only when the node is a leaf (no left or right child). Apply this function to both trees to get their leaf sequences, then compare these sequences directly for equality…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each tree is traversed once in DFS, visiting every node exactly once, resulting in linear time proportional to the total number of nodes.
Space
O(h)
The recursion stack uses O(h) auxiliary space, where h is the height of the tree, due to the depth-first traversal. The leaf lists use O(l) space, where l is the number of leaves, which is unavoidable for storing the output sequences.
Pattern Spotlight
DFS (Leaf Node Collection)
When comparing tree leaf sequences, use DFS to extract leaves in order by recording values only at nodes without children, then compare the resulting sequences directly.
Solution
| 1 | class Solution: |
| 2 | def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool: |
| 3 | def get_leaves(root): |
| 4 | leaves = [] |
| 5 | |
| 6 | def dfs(node): |
| 7 | if not node: |
| 8 | return |
| 9 | |
| 10 | if not node.left and not node.right: |
| 11 | leaves.append(node.val) |
| 12 | return |
| 13 | |
| 14 | dfs(node.left) |
| 15 | dfs(node.right) |
| 16 | |
| 17 | dfs(root) |
| 18 | return leaves |
| 19 | |
| 20 | return get_leaves(root1) == get_leaves(root2) |
Step-by-Step Solution
Extract Leaf Values from a Tree Using Recursive DFS
| 3 | def get_leaves(root): |
| 4 | leaves = [] |
| 6 | def dfs(node): |
| 7 | if not node: |
| 8 | return |
| 10 | if not node.left and not node.right: |
| 11 | leaves.append(node.val) |
| 12 | return |
| 14 | dfs(node.left) |
| 15 | dfs(node.right) |
| 17 | dfs(root) |
| 18 | return leaves |
Objective
To traverse the tree recursively and collect the values of all leaf nodes in left-to-right order.
Key Insight
A node is a leaf if it has no left or right children. By recursively traversing left and right subtrees and appending values only at leaves, the algorithm naturally collects leaf values in the correct order. This approach leverages the call stack to maintain traversal state without extra data structures.
Interview Quick-Check
Core Logic
The DFS function visits each node, appending its value to the leaf list only if it has no children, ensuring the leaf sequence is collected in left-to-right order.
State & Boundaries
The base case returns immediately when a null node is encountered, preventing unnecessary recursion.
Common Pitfalls & Bugs
Failing to check for leaf nodes before recursing can lead to incorrect leaf sequences or missing leaves.
Compare Leaf Sequences of Both Trees for Equality
To determine if the two trees are leaf-similar by comparing their extracted leaf sequences.
1 more step with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
return get_leaves(root1) == get_leaves(root2)Compare the leaf sequences of both trees and return the result.
Directly comparing the two leaf lists determines if the trees are leaf-similar, fulfilling the problem's requirement with a simple and efficient operation.
returnCheck if the current node is a leaf (no left or right child).
Identifying leaf nodes is critical because only their values should be recorded for the leaf sequence.
if not node.left and not node.right:Append the leaf node's value to the leaves list.
Recording the leaf value at the correct traversal point ensures the leaf sequence reflects the left-to-right order of leaves.
Full line-by-line criticality + rationale for all 13 lines available on Pro.
Test Your Understanding
Why is it sufficient to compare only the leaf value sequences of two trees to determine if they are leaf-similar?
See the answer with Pro.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Leaf-Similar Trees from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Leaf-Similar Trees drill