LeetCode 872: Leaf-Similar Trees

Problem Restatement

We are given the roots of two binary trees:

root1
root2

For each tree, collect all leaf values from left to right.

A leaf node is a node with no left child and no right child.

Two trees are leaf-similar if their leaf value sequences are the same.

Return True if the two trees are leaf-similar. Otherwise, return False.

Input and Output

Item	Meaning
Input	`root1`, the root of the first binary tree
Input	`root2`, the root of the second binary tree
Output	`True` if both trees have the same leaf sequence
Leaf node	A node with no children

Function shape:

class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        ...

Examples

Example 1:

root1 = [3, 5, 1, 6, 2, 9, 8, None, None, 7, 4]
root2 = [3, 5, 1, 6, 7, 4, 2, None, None, None, None, None, None, 9, 8]

The leaf value sequence of root1 is:

[6, 7, 4, 9, 8]

The leaf value sequence of root2 is also:

[6, 7, 4, 9, 8]

So the answer is:

True

Example 2:

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

The leaf value sequence of root1 is:

[2, 3]

The leaf value sequence of root2 is:

[3, 2]

The sequences are different, so the answer is:

False

First Thought: Compare Tree Shapes

The two trees do not need to have the same structure.

Only the leaf values matter, and only in left-to-right order.

So comparing tree shape, height, or internal node values is unnecessary.

We should extract the leaf sequence from each tree, then compare the two sequences.

Key Insight

A DFS traversal that visits the left child before the right child naturally sees leaves from left to right.

For each node:

If the node is None, stop.
If the node has no children, append its value.
Otherwise, visit the left subtree, then the right subtree.

After doing this for both trees, compare the two lists.

Algorithm

Define a helper function:

collect_leaves(node, leaves)

For each node:

If node is None, return.
If node.left and node.right are both None, append node.val.
Recursively visit node.left.
Recursively visit node.right.

Then:

Create leaves1.
Create leaves2.
Collect leaves from root1 into leaves1.
Collect leaves from root2 into leaves2.
Return whether the lists are equal.

Correctness

The helper function appends a node value only when the node has no children, so every appended value is a leaf value.

The helper visits the left subtree before the right subtree. Therefore, leaves are appended in left-to-right order.

Every node is visited once, so every leaf is considered exactly once.

After collecting leaves from both trees, the two trees are leaf-similar exactly when the two collected sequences are equal. The algorithm returns that comparison, so it is correct.

Complexity

Let:

n = number of nodes in root1
m = number of nodes in root2

Metric	Value	Why
Time	`O(n + m)`	Each node in both trees is visited once
Space	`O(n + m)`	Leaf lists and recursion stack storage

More precisely, the lists store only leaf values, and the recursion stack uses the tree heights.

Implementation

from typing import Optional

# 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: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def collect_leaves(node: Optional[TreeNode], leaves: list[int]) -> None:
            if node is None:
                return

            if node.left is None and node.right is None:
                leaves.append(node.val)
                return

            collect_leaves(node.left, leaves)
            collect_leaves(node.right, leaves)

        leaves1 = []
        leaves2 = []

        collect_leaves(root1, leaves1)
        collect_leaves(root2, leaves2)

        return leaves1 == leaves2

Code Explanation

The helper starts with the empty-node case:

if node is None:
    return

Then it checks whether the current node is a leaf:

if node.left is None and node.right is None:
    leaves.append(node.val)
    return

The return is useful because a leaf has no children to visit.

For internal nodes, we visit left before right:

collect_leaves(node.left, leaves)
collect_leaves(node.right, leaves)

This preserves the required left-to-right leaf order.

Then we collect both sequences:

leaves1 = []
leaves2 = []

collect_leaves(root1, leaves1)
collect_leaves(root2, leaves2)

Finally, compare them:

return leaves1 == leaves2

Testing

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def test_leaf_similar():
    s = Solution()

    root1 = TreeNode(3)
    root1.left = TreeNode(5)
    root1.right = TreeNode(1)
    root1.left.left = TreeNode(6)
    root1.left.right = TreeNode(2)
    root1.right.left = TreeNode(9)
    root1.right.right = TreeNode(8)
    root1.left.right.left = TreeNode(7)
    root1.left.right.right = TreeNode(4)

    root2 = TreeNode(3)
    root2.left = TreeNode(5)
    root2.right = TreeNode(1)
    root2.left.left = TreeNode(6)
    root2.left.right = TreeNode(7)
    root2.right.left = TreeNode(4)
    root2.right.right = TreeNode(2)
    root2.right.right.left = TreeNode(9)
    root2.right.right.right = TreeNode(8)

    assert s.leafSimilar(root1, root2) is True

    root1 = TreeNode(1, TreeNode(2), TreeNode(3))
    root2 = TreeNode(1, TreeNode(3), TreeNode(2))

    assert s.leafSimilar(root1, root2) is False

    root1 = TreeNode(1)
    root2 = TreeNode(1)

    assert s.leafSimilar(root1, root2) is True

    root1 = TreeNode(1)
    root2 = TreeNode(2)

    assert s.leafSimilar(root1, root2) is False

    print("all tests passed")

test_leaf_similar()

Test meaning:

Test	Why
Same leaf sequence, different shape	Checks the main requirement
Same leaves in different order	Order matters
Single equal nodes	Minimum matching case
Single different nodes	Minimum non-matching case