Leaf-Similar Trees
Easy · Trees · Tree · Depth-First Search · Binary Tree
Problem
The leaf value sequence of a binary tree lists the values of its leaves (nodes with no children) from left to right.
Two binary trees are leaf-similar when their leaf value sequences are identical: the same values in the same order. Given root1 and root2, return true if the two trees are leaf-similar.
Trees are shown as level-order lists, with null for a missing child.
Examples
Input: root1 = [5,2,8,1,3], root2 = [9,1,4,null,null,3,8] Output: true
In the first tree 2 has the leaves 1 and 3, and 8 is a leaf. In the second, 1 is a leaf and 4 has the leaves 3 and 8. Both read 1, 3, 8.
Input: root1 = [5,2,8], root2 = [5,8,2] Output: false
The sequences are [2, 8] and [8, 2]: the same values in a different order.
Constraints
- 1 <= number of nodes in each tree <= 200
- 0 <= Node.val <= 200
Approaches
- Collect both leaf sequences — time O(n1 + n2), space O(n1 + n2)
Follow-up
What if the trees were huge and very likely to differ early? The lazy version stops at the first mismatched leaf and keeps only a root-to-leaf path per tree, so it never builds the full sequences.
Related problems
Start free on Cariara · Coding problems · System design studio
