Problem Overview
LeetCode 872 Leaf-Similar Trees asks you to determine whether two binary trees are "leaf-similar." Two trees are leaf-similar if and only if their leaf value sequences — reading leaves from left to right — are identical, regardless of how different the overall tree structures may be.
A leaf node is any node that has no left child and no right child. The leaf sequence of a tree is formed by collecting all leaf values in a left-to-right traversal (i.e., the order in which a DFS encounters them). Two trees with completely different shapes can still be leaf-similar if their leaves line up in the same order.
The problem is rated Easy on LeetCode, but it tests your ability to extract a specific traversal property from a tree. The key insight is that you do not need to compare the trees structurally at all — only their leaf sequences matter.
- Two trees are leaf-similar if their leaf value sequences match left to right
- A leaf is a node with no left child and no right child
- Trees can have entirely different shapes and still be leaf-similar
- Constraints: 1 to 200 nodes per tree, values in [0, 200]
- Return true if the leaf sequences are equal, false otherwise
Collect and Compare
The straightforward approach is to run DFS on tree1, collecting all leaf values into a list in the order encountered. Then run DFS on tree2, collecting its leaves into a second list. Finally compare the two lists — if they are equal, return true; otherwise false.
DFS naturally visits nodes in left-to-right order when you recurse left before right. This means leaves are automatically appended in the correct sequence without any sorting or reordering. The two lists can then be compared with a single equality check.
This two-pass approach is easy to reason about and implement correctly. The time complexity is O(n+m) where n and m are the sizes of the two trees, and space is O(n+m) for the two leaf lists plus the recursion stack.
Key Insight
A leaf is a node with no children — check both left and right are None/null. DFS naturally visits leaves left-to-right when you recurse left before right. Collecting into a list then comparing with == is the simplest and most interview-friendly approach.
DFS Leaf Collection
The DFS helper function is concise: if the current node is null, return immediately. If the node has no left child and no right child, it is a leaf — append its value to the result list. Otherwise, recurse into the left subtree and then the right subtree.
By always recursing left before right, the leaves are collected in left-to-right order automatically. There is no need to sort or post-process the leaf list. The recursion bottoms out at leaves and null nodes, making the base cases clear and simple.
In Python: def getLeaves(node, leaves): if not node: return; if not node.left and not node.right: leaves.append(node.val); return; getLeaves(node.left, leaves); getLeaves(node.right, leaves). Call this for both trees and compare the resulting lists.
- 1If node is null — return immediately (base case)
- 2If node has no left child and no right child — it is a leaf, append node.val to the list
- 3Otherwise — recurse into node.left (collecting left-side leaves first)
- 4Then recurse into node.right (collecting right-side leaves second)
- 5After DFS completes the list contains all leaves in left-to-right order
Generator/Yield Optimization
Python generators offer an elegant optimization: instead of collecting all leaves into a list, yield each leaf lazily as DFS encounters it. You can then use itertools.zip_longest to compare leaves from both trees one by one, short-circuiting as soon as a mismatch is found.
The generator version: def leaves(node): if not node: return; if not node.left and not node.right: yield node.val; return; yield from leaves(node.left); yield from leaves(node.right). Then: return all(a == b for a, b in zip_longest(leaves(root1), leaves(root2))) — this stops at the first mismatch and never collects lists of unequal length.
The generator approach is O(h1 + h2) extra space for the two generator stacks (where h is tree height) versus O(n+m) for the list approach. For balanced trees this is O(log n + log m) space, a significant improvement over O(n+m). However it is slightly harder to explain in an interview under time pressure.
Generator Trade-offs
The generator approach uses O(1) extra list space and short-circuits on the first mismatch — ideal for very large trees. But for interviews, the list approach is clearer, equally fast for small trees, and easier to write correctly under pressure. Know both; default to lists unless space is explicitly constrained.
Walk-Through Example
Example 1 from LeetCode: tree1 has leaves [6, 7, 4, 9, 8] read left-to-right. Tree2 has leaves [6, 7, 4, 9, 8] read left-to-right. The sequences are identical so the function returns true even though the two trees have very different shapes and internal node values.
Example 2: tree1 has leaves [1, 2] and tree2 has leaves [2, 1]. The sequences differ — same values but different order — so the function returns false. This illustrates that leaf-similarity is order-sensitive: left-to-right ordering must match exactly.
Edge case: a tree with a single node (the root is also the only leaf). Its leaf sequence is just [root.val]. Two single-node trees are leaf-similar if and only if they have the same value.
- 1tree1 DFS: visit left subtrees first → leaves = [6, 7, 4, 9, 8]
- 2tree2 DFS: visit left subtrees first → leaves = [6, 7, 4, 9, 8]
- 3[6,7,4,9,8] == [6,7,4,9,8] → return true
- 4Counter-example: tree1 leaves=[1,2], tree2 leaves=[2,1] → [1,2] != [2,1] → return false
- 5Single-node trees: leaf sequence = [root.val]; equal iff same value
Code Walkthrough: Python and Java
Python list version: define getLeaves(node, acc) as a helper; call it on both roots; return leaves1 == leaves2. One-liner using a nested helper and list comprehension is possible but the explicit helper is clearest. Complexity: O(n+m) time, O(n+m) space for the two leaf lists.
Python generator version: def leaves(node): if not node: return; if not node.left and not node.right: yield node.val; return; yield from leaves(node.left); yield from leaves(node.right). Main: from itertools import zip_longest; return all(a==b for a,b in zip_longest(leaves(root1), leaves(root2))). Space: O(h) for generator stacks.
Java version: use a helper void collectLeaves(TreeNode node, List<Integer> list). Check node == null return; check node.left == null && node.right == null to identify leaves; otherwise recurse left then right. Main: List<Integer> l1 = new ArrayList<>(), l2 = new ArrayList<>(); collectLeaves(root1, l1); collectLeaves(root2, l2); return l1.equals(l2). Complexity: O(n+m) time, O(n+m) space.
Do Not Compare Tree Structure
Never compare internal node values or tree shapes — two very different trees can have identical leaf sequences. Only leaves matter. Ensure your leaf check is strictly: node.left == null AND node.right == null. A node with only one child is NOT a leaf and must not be collected.