Leaf-Similar Trees

Problem

Reading a binary tree’s leaves from left to right gives its leaf value sequence. Two trees are leaf-similar when their leaf value sequences are identical. Given the roots of two binary trees, root1 and root2, return True if they are leaf-similar, False otherwise.

The trees’ internal structure may differ arbitrarily — only the ordered list of leaf values matters.

Examples

Example 1

root1:        3                 root2:        3
            /   \                           /   \
           5     1                         5     1
          / \   / \                       / \   / \
         6   2 9   8                     6   7 4   2
            / \                                   / \
           7   4                                 9   8

Output: True

Both leaf sequences are [6, 7, 4, 9, 8] even though the shapes differ.

Example 2

root1: [1,2,3]      root2: [1,3,2]

    1                   1
   / \                 / \
  2   3               3   2

Output: False

Leaf sequences [2, 3] vs [3, 2] — same values, wrong order.

Constraints

• Each tree has 1 to 200 nodes — tiny; clarity beats micro-optimization.
• 0 <= Node.val <= 200 — duplicate values are possible, so compare sequences, not sets.

Think about it first

TL;DR

DFS each tree collecting leaves left-to-right, compare the two lists — O(n1 + n2) time, O(n1 + n2) space (O(h) with lock-step generators).

Approach 1 — Brute force: collect both leaf sequences and compare

The direct translation of the definition: run a depth-first search (DFS) — the classical traversal that explores each branch fully before backtracking, which visits leaves in left-to-right order — on each tree, append every leaf’s value to a list, and compare the lists. For this problem the “brute force” is already asymptotically optimal; the later approach only improves memory.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional, List


class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def leaves(node: Optional[TreeNode], out: List[int]) -> None:
            if not node:
                return
            if not node.left and not node.right:
                out.append(node.val)
                return
            leaves(node.left, out)
            leaves(node.right, out)

        seq1: List[int] = []
        seq2: List[int] = []
        leaves(root1, seq1)
        leaves(root2, seq2)
        return seq1 == seq2

Walkthrough on example 1: DFS on root1 goes 3 → 5 → 6 (leaf, append 6), backtracks to 5 → 2 → 7 (append 7), 4 (append 4), then 3 → 1 → 9 (append 9), 8 (append 8) → seq1 = [6, 7, 4, 9, 8]. The same walk on root2 yields [6, 7, 4, 9, 8]. Lists are equal → True.

Complexity: O(n1 + n2) time, O(n1 + n2) space for the two leaf lists plus O(h) recursion. With ≤200 nodes per tree nothing “kills” this — the follow-up value is purely the space refinement below.

Approach 2 — Lock-step comparison with generators

The insight: you don’t need either full sequence in memory — you only need the next leaf of each tree at a time. Python generators are lazy iterators that pause a DFS mid-traversal; advancing two of them in lock-step compares the sequences using only the two recursion stacks, and can also exit early on the first mismatch.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from itertools import zip_longest
from typing import Optional, Iterator


class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def leaves(node: Optional[TreeNode]) -> Iterator[int]:
            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)

        # zip_longest so a longer sequence (extra leaves) can't be silently truncated
        return all(a == b for a, b in zip_longest(leaves(root1), leaves(root2)))

Walkthrough on example 2 (root1 = [1,2,3], root2 = [1,3,2]): the first next() on each generator runs each DFS just far enough to reach the first leaf — 2 from tree 1 and 3 from tree 2. 2 == 3 is false, all(...) short-circuits, and the answer is False without ever visiting the remaining leaves.

Complexity: O(n1 + n2) time worst case with early exit on the first mismatch; O(h1 + h2) space — only the paused DFS stacks, no leaf lists.

Approach 3 — Iterative DFS with explicit stacks (no recursion)

The insight: the same lock-step idea works with two explicit stacks: repeatedly pop down to the next leaf of each tree, compare, repeat — the standard recursion-free formulation, immune to recursion limits.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional, List


class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def next_leaf(stack: List[TreeNode]) -> Optional[int]:
            while stack:
                node = stack.pop()
                if not node.left and not node.right:
                    return node.val
                # push right first so left is explored first (left-to-right leaves)
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
            return None

        s1: List[TreeNode] = [root1]
        s2: List[TreeNode] = [root2]
        while s1 or s2:
            if next_leaf(s1) != next_leaf(s2):
                return False
        return True

Walkthrough on example 1: next_leaf(s1) pops 3, pushes 1 then 5; pops 5, pushes 2 then 6; pops 6 — leaf, returns 6. next_leaf(s2) likewise returns 6. The loop keeps yielding matched pairs (7,7), (4,4), (9,9), (8,8); both stacks empty out together, later calls return None == None, and the loop ends → True.

Complexity: O(n1 + n2) time, O(h1 + h2) stack space.

Common pitfalls

• Comparing concatenated strings of leaf values: sequences [12, 3] and [1, 23] both concatenate to "123" — join with a separator or compare lists.
• Comparing sets or sorted lists: order matters (example 2) and duplicates matter.
• Length mismatch bugs in lock-step versions: plain zip stops at the shorter sequence, so [6,7] vs [6,7,4] would wrongly pass — use zip_longest or an explicit both-exhausted check.
• Pushing left before right in the iterative stack version, which reverses the leaf order.

Pattern takeaway

“Compare two trees by some derived sequence” decomposes into: (1) pick the traversal that produces the sequence in the required order — plain DFS gives left-to-right leaves — and (2) compare sequences, not sets or concatenations. When only equality of streams is needed, generators let you compare lazily in O(h) space with early exit — a trick that generalizes to any pair of same-order traversals (BST iterators, inorder streams, file diffs).