872. Leaf-Similar Trees

Easy · solved 2026-10-05 · Open on LeetCode

treebinary-treedfs

Time O(n₁ + n₂) · Space O(h₁ + h₂)

How to get there

Walk both trees in step, one leaf at a time

1. Restate what is compared. Only the leaves count, read left to right. Two trees of different shapes are leaf-similar when those sequences are equal.

2. Compare LeetCode’s first example by hand and find where the obvious way wastes memory. The trees have different shapes, but both have the leaves 6, 7, 4, 9, 8 in that order. The obvious way collects each tree’s leaves into a list and compares the lists. That stores every leaf of both trees, yet the comparison only ever looks at one pair at a time.

3. Find what to remember instead. Where each walk has got to, so it can be paused after a leaf and resumed for the next. A plain recursive function can’t hand back one leaf and resume later, but an explicit stack can: the stack is the walk’s place. One stack per tree, and the two walks take turns.

4. Make each walk reach its leaves left to right. A depth-first walk that pushes the right child before the left pops the left first, so it reaches leaves in left-to-right order.

5. Step the walks together. Every time tree 1’s walk reaches a leaf, advance tree 2’s walk to its next leaf and compare the two. A mismatch, or tree 2 running out first, settles it as False. When tree 1 is done, tree 2 must have no leaves left either.

6. Check the cost. Each node is pushed and popped once: O(n₁ + n₂) time. Each stack holds only the pending right children along one path, O(h₁ + h₂) space, and the walk stops at the first mismatch.

The reusable recipe: to compare the sequences two walks produce, keep each walk’s own stack and advance them in turn, comparing as you go. Memory then follows the walks’ depth, not the sequences’ length.

Let the stacks' meaning settle the three exits

Variable	Always means, at the top of the outer loop
`stack1`, `stack2`	the subtrees of each tree not yet walked, the leftmost on top
the two walks	have produced the same number of leaves so far, and they matched pair by pair

Every node on a stack is the root of a subtree, and every subtree has at least one leaf. So a stack is empty exactly when its tree has no leaves left. That one fact decides all three exits:

Code	What happened	Answer
`if not stack2: return False`	tree 1 reached a leaf, and tree 2 has none left	tree 1 has more leaves
`if current1.val != current2.val: return False`	the next leaves of the two trees differ	the sequences differ
`return not stack2`	tree 1 has no leaves left	similar only if tree 2 has none left either

Inside the inner loop, break after a match returns to tree 1 with both walks one leaf further, so the second row of the first table holds again. The inner loop can never empty stack2 without reaching a leaf, by the same fact.

The method carries over: say what an empty stack means, and each exit follows from it.

Alternatives compared

Approach	Time	Space	How it works
Collect both leaf lists	O(n₁ + n₂)	O(n₁ + n₂)	Walk each tree fully, append its leaves to a list, and compare the lists.
Two stacks in lockstep (chosen, `solution.py`)	O(n₁ + n₂)	O(h₁ + h₂)	Walk both trees with their own stacks, one leaf at a time, and stop at the first mismatch.
Two leaf generators	O(n₁ + n₂)	O(h₁ + h₂)	Write the walk once as a generator that yields each leaf, then compare the two generators pair by pair with `itertools.zip_longest`.

The lists are the simplest to write, but they hold every leaf and always walk both trees to the end. The stacks and the generators keep only each walk’s place; a generator writes the walk once, where the stacks write it twice.

solution.py

# 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
class Solution:
    def leafSimilar(self, root1: TreeNode | None, root2: TreeNode | None) -> bool:
        stack1, stack2 = [root1], [root2]

        while stack1:
            current1 = stack1.pop()
            if current1.right:
                stack1.append(current1.right)
            if current1.left:
                stack1.append(current1.left)
            if not current1.left and not current1.right:
                if not stack2:
                    return False
                while stack2:
                    current2 = stack2.pop()
                    if current2.right:
                        stack2.append(current2.right)
                    if current2.left:
                        stack2.append(current2.left)
                    if not current2.left and not current2.right:
                        if current1.val != current2.val:
                            return False
                        else:
                            break

        return not stack2

Notes

Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.