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.
• 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

This translates the definition directly. A depth-first search (DFS) explores each branch fully before backtracking, so it visits leaves in left-to-right order. Run one on each tree, append every leaf’s value to a list, and compare the lists. The brute force is already asymptotically optimal here; the later approaches only improve memory.

A DFS over root1 from example 1, with the leaves it collects marked:

flowchart TD
  n3((3)) --> n5((5))
  n3 --> n1((1))
  n5 --> n6((6))
  n5 --> n2((2))
  n2 --> n7((7))
  n2 --> n4((4))
  n1 --> n9((9))
  n1 --> n8((8))
  classDef leaf fill:#dcedc8,stroke:#558b2f;
  class n6,n7,n4,n9,n8 leaf;

Reading the marked leaves left to right gives [6, 7, 4, 9, 8].

# 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


def leafSimilar(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 this is fine; the follow-up only refines space.

Approach 2 — Lock-step comparison with generators

You don’t need either full sequence in memory, only 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 exits 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


def leafSimilar(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 same lock-step idea works with two explicit stacks: repeatedly pop down to the next leaf of each tree, compare, and repeat. This is 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


def leafSimilar(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 two steps: (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, which generalizes to any pair of same-order traversals such as BST iterators or inorder streams.