Leaf-Similar Trees
Leaf-Similar Trees: return true if two binary trees have the same leaf value sequence when their leaves are read from left to right.
- The number of nodes in each tree is in the range [1, 200].
- Both trees have values in the range [0, 200].
Intuition
Leaf similar trees asks whether two binary trees produce the same sequence of leaf values, read left to right. That sequence is called the leaf value sequence, and comparing it is the whole problem.
The framing that makes this easy is to stop thinking about trees and think about lists:
- Collect each tree's leaves into a list, then compare the two lists — the tree structure above the leaves is irrelevant.
Two trees of completely different shapes are leaf-similar as long as their leaves read the same. Trying to compare the trees structurally answers a different question entirely.
Collecting the leaves is a DFS. The traversal must visit left before right at every node, since the sequence is defined in left-to-right order — swapping the recursion order reverses parts of the sequence and produces wrong answers on asymmetric trees.
A leaf is a node with both children null. The common error is testing only one child, which wrongly treats a node with a single child as a leaf and injects an internal value into the sequence.
Any of the three DFS orders works, because a leaf has no children and so occupies the same relative position in preorder, inorder, and postorder. What matters is only that left is explored before right.
Both lists must be compared element by element in order, not as sets or by length. [1, 2] and [2, 1] have the same values and the same length but are not leaf-similar.
Collecting both lists fully before comparing is simplest. Generators allow early exit on the first mismatch, saving work on large dissimilar trees, at the cost of more complex code.
Reducing a tree to a canonical sequence and comparing is the recurring move whenever two trees must be judged equivalent under some relaxation. The tell is that the question mentions a specific traversal order — here 'from left to right', which names DFS with left before right.
Approach
Before reading on: which traversal order visits the leaves left to right, and does it matter whether you record values before or after recursing? Aim for O(n + m).
Reduce the trees to lists
Collect each tree's leaf values into a list and compare them. The structure above the leaves is irrelevant — trees of entirely different shapes can be leaf-similar.
Traverse left before right
The sequence is defined left to right, so the recursion must visit the left child first. Swapping the order reverses parts of the sequence on asymmetric trees.
Test both children for a leaf
A leaf has both children null. Checking only one child wrongly treats a single-child node as a leaf and injects an internal value into the sequence.
Use any DFS order
A leaf has no children, so it sits in the same relative position in preorder, inorder, and postorder. Only the left-before-right rule matters.
Compare in order
Compare the lists element by element, not as sets or by length. [1, 2] and [2, 1] share values and length but are not leaf-similar.
Cost of the comparison
Both trees are traversed once, giving O(m + n) time. Space is O(m + n) for the leaf lists plus O(h) for the recursion stack.
Solution & live demo
Common pitfalls
Collecting every node, not just leaves
return [node.val] + leaves(node.left) + leaves(node.right)
if not node.left and not node.right:
return [node.val]
return leaves(node.left) + leaves(node.right)Internal values are irrelevant to leaf similarity. Including them makes two genuinely leaf-similar trees of different shapes compare unequal.
Testing only one child for leafness
if not node.left:
return [node.val]if not node.left and not node.right:
return [node.val]A node with only a right child is not a leaf. Checking one side treats it as one and stops the traversal early, dropping every leaf beneath it.
Comparing as sets or sorted lists
return sorted(leaves(root1)) == sorted(leaves(root2))
return leaves(root1) == leaves(root2)
The sequence is ordered by definition. Sorting or set-comparing would call [1,2] and [2,1] similar, but their left-to-right leaf sequences are different.
Edge cases
The root itself is a leaf, so each sequence has one value.
Structure is ignored entirely; only the leaf order matters, so these are similar.
The sequences differ positionally, so the answer is false.
The lists have different lengths and compare unequal.
DFS still yields the single leaf at the bottom; recursion depth is O(n) in the worst case.