# LeetCode 872: Leaf-Similar Trees

## Problem Restatement

We are given the roots of two binary trees:

```python
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:

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

## Examples

Example 1:

```python
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:

```python
[6, 7, 4, 9, 8]
```

The leaf value sequence of `root2` is also:

```python
[6, 7, 4, 9, 8]
```

So the answer is:

```python
True
```

Example 2:

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

The leaf value sequence of `root1` is:

```python
[2, 3]
```

The leaf value sequence of `root2` is:

```python
[3, 2]
```

The sequences are different, so the answer is:

```python
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:

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

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

## Algorithm

Define a helper function:

```python
collect_leaves(node, leaves)
```

For each node:

1. If `node` is `None`, return.
2. If `node.left` and `node.right` are both `None`, append `node.val`.
3. Recursively visit `node.left`.
4. Recursively visit `node.right`.

Then:

1. Create `leaves1`.
2. Create `leaves2`.
3. Collect leaves from `root1` into `leaves1`.
4. Collect leaves from `root2` into `leaves2`.
5. 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:

```python
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

```python
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:

```python
if node is None:
    return
```

Then it checks whether the current node is a leaf:

```python
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:

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

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

Then we collect both sequences:

```python
leaves1 = []
leaves2 = []

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

Finally, compare them:

```python
return leaves1 == leaves2
```

## Testing

```python
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 |