Leaf-Similar Trees: Comparing Leaf Sequences

You are given the roots of two binary trees. A leaf is a node with no children. The leaf value sequence is the list of leaf node values read from left to right. Two trees are leaf-similar if their leaf value sequences are identical. Return True if the two trees are leaf-similar, and False otherwise.

This is LeetCode 872: Leaf-Similar Trees. The key insight is that two trees can have completely different shapes and internal node values, yet still be leaf-similar as long as their leaves appear in the same left-to-right order.

Why this problem matters

Leaf-Similar Trees teaches you to separate what you collect from how you traverse. The tree structure is irrelevant to the answer. Only the leaves matter, and only their left-to-right order matters. This "collect a specific subset during traversal" pattern shows up constantly: finding all paths, gathering nodes at a certain depth, or filtering nodes by some property. The underlying traversal is always DFS. The only thing that changes is the condition for adding a node to your result.

Once you can write a DFS that collects leaves, you can adapt it to collect anything.

The approach

The algorithm has two phases:

1. Collect leaves from tree 1. Run a DFS (depth-first search) on the first tree. Whenever you reach a node with no left child and no right child, append its value to a list. Because DFS visits the left subtree before the right subtree, the leaves land in left-to-right order automatically.
2. Collect leaves from tree 2. Do the same DFS on the second tree, building a second list.
3. Compare the two lists. If they are equal, the trees are leaf-similar.

The solution

def leaf_similar(root1, root2):
    def get_leaves(node):
        if not node:
            return []
        if not node.left and not node.right:
            return [node.val]
        return get_leaves(node.left) + get_leaves(node.right)

    return get_leaves(root1) == get_leaves(root2)

Visual walkthrough

Let's trace through two trees step by step. Tree 1 has root 1 with structure [1, 2, 3, 4] and Tree 2 has root 5 with structure [5, 6, 3, null, 4]. Both trees have different shapes and different internal values, but we will see that their leaf sequences match.

The DFS visits nodes in a predictable order. Every time it reaches a node with no children, that node is a leaf and gets added to the list. After collecting from both trees, a simple equality check gives you the answer.

Complexity analysis

Time is O(n + m), where n is the number of nodes in tree 1 and m is the number of nodes in tree 2. You visit every node in both trees exactly once during the DFS traversals.

Space is O(n + m). The leaf lists can hold at most n/2 and m/2 entries respectively (a complete binary tree has roughly half its nodes as leaves). The recursion stack adds O(h1 + h2) where h1 and h2 are the heights of the trees. In the worst case (skewed trees), the stack alone is O(n) or O(m).

Building blocks

This problem is built on two fundamental bricks:

1. DFS leaf collection. A recursive DFS that checks whether the current node is a leaf (no left child, no right child) and, if so, appends its value to a result list. This pattern is the foundation for any problem that asks you to find, count, or compare leaf nodes. You will reuse it in problems like Sum of Left Leaves and Minimum Depth of Binary Tree.

2. Sequence comparison. After collecting two lists, you compare them element by element. In Python, list1 == list2 handles this in one expression, but the concept applies broadly. Many tree problems reduce to "collect something from each tree and compare the results."

Edge cases to watch for

Before submitting, consider these:

• Both trees are a single node. Each tree has exactly one leaf (the root). If the root values match, return True.
• One tree is much deeper than the other. The shapes do not matter. Only the leaf sequences matter. A deep, skinny tree and a wide, shallow tree can still be leaf-similar.
• All internal nodes have the same value. Do not confuse internal nodes with leaves. Only nodes with no children count as leaves.
• Different number of leaves. If tree 1 has three leaves and tree 2 has four, the sequences have different lengths and cannot be equal.
• Same leaf values but different order. [2, 3] is not the same as [3, 2]. Order matters because "left to right" is part of the definition.

From understanding to recall

You just traced through a clean leaf-collection DFS. The helper function makes sense. The comparison is simple. But will you reproduce this in an interview without hesitation? Will you instinctively write the leaf check as not node.left and not node.right instead of forgetting one side? Will you remember that DFS gives you left-to-right order for free?

Understanding is the first step. Recall under pressure is the second. Spaced repetition bridges the gap. You type the solution from scratch at increasing intervals: after one day, then three days, then a week. Each repetition reinforces the leaf check, the recursive concatenation, and the final comparison until they become automatic.

The DFS leaf collection pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition beats grinding random problems every time.

Related posts

• Same Tree - Compares two trees node by node with parallel recursion
• Symmetric Tree - Uses DFS to compare mirror pairs within a single tree
• Binary Tree Inorder Traversal - Another DFS traversal that collects node values in a specific order