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
The shape of each tree is irrelevant — only the ordered list of leaf values matters. A depth-first traversal that visits left before right produces exactly that left-to-right order, so collect both sequences and compare them.
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).
Identify what a leaf is, and what order means
A leaf is a node with no left and no right child. 'Left to right' refers to their horizontal arrangement in the drawn tree, which is precisely the order a DFS produces when it recurses left before right. Any of preorder, inorder, or postorder gives the same leaf sequence, because leaves have no children to interleave — the only thing that matters is that left is explored before right.
Collect, then compare
Run a recursive DFS on each tree. At a leaf, append the value; otherwise recurse into whichever children exist. That gives two lists. Compare them with a single equality test — they match only if they have the same length and the same values in the same order. Building both lists in full is O(n + m) time and clean to reason about.
Early exit and the space trade-off
The straightforward version stores both sequences, costing O(n + m) space plus recursion depth. If memory mattered you could generate both lazily and compare element by element, stopping at the first mismatch — Python generators make that natural. It is rarely worth the extra complexity here, since the constraints cap the trees at 200 nodes, but knowing the option exists is the useful part.
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.