Leaf-Similar Trees — Solution

Problem

Two binary trees are "leaf-similar" if the sequence of their leaf values, read left to right, is identical. A leaf is any node with no children.

The two trees below both produce the leaf sequence [6, 7, 4, 9, 8]:

[3,5,1,6,2,9,8,null,null,7,4]

[3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]

• Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
• Output: true
• Explanation: both trees share the same left-to-right leaf sequence: 6, 7, 4, 9, 8.

Counter-example — root1 = [1,2,3], root2 = [1,3,2] returns false because the first tree's leaves are [2, 3] and the second's are [3, 2].

Intuition

Reading leaves left to right is exactly what a depth-first traversal produces when you always recurse left before right and record a node only when it has no children. Collect that sequence for each tree independently, then compare the two lists.

Solution — DFS Leaf Collection

Recursively traverse each tree; record a node's value only when both children are null. Run this on both trees and compare the resulting lists.

1. Define a helper that takes a node and a running leaf list.
2. If the node is null, return immediately.
3. If the node has no left child and no right child, it is a leaf — append its value and return.
4. Otherwise recurse into the left subtree, then the right subtree.
5. Collect leaves for both trees, then return whether the two lists are equal.

1from typing import Optional
2
3class Solution:
4    def leafSimilar(self, root1: Optional['TreeNode'], root2: Optional['TreeNode']) -> bool:
5        def collect_leaves(node, leaves):
6            if node is None:
7                return
8            if node.left is None and node.right is None:  # both children absent: leaf
9                leaves.append(node.val)
10                return
11            collect_leaves(node.left, leaves)
12            collect_leaves(node.right, leaves)
13
14        leaves1, leaves2 = [], []
15        collect_leaves(root1, leaves1)
16        collect_leaves(root2, leaves2)
17        return leaves1 == leaves2

Time: O(n₁ + n₂) — every node in both trees is visited exactly once.
Space: O(n₁ + n₂) — O(h₁ + h₂) for the recursion stacks plus O(L) for the two leaf lists, where h is tree height and L is total leaf count.

Complexity Summary

Common Mistakes

• Using BFS instead of DFS to collect leaves — BFS processes nodes level by level, so it encounters all shallower leaves before deeper ones. In tree 1 of the example, BFS would yield [6, 9, 8, 7, 4] (level-2 leaves first, then level-3 leaves), not [6, 7, 4, 9, 8]. The left-to-right leaf sequence requires DFS.
• Treating a node with one null child as a leaf — a leaf requires both children to be null. A node that has only a left child is an internal node, not a leaf, so the check must be left == null AND right == null, not left == null OR right == null.
• Checking if not node.val to test for null in Python — this evaluates to True when node.val is 0, causing valid leaf nodes to be skipped. Always test the node reference itself: if node is None or if not node.
• Recursing right before left — the left-to-right leaf ordering depends on visiting the left subtree first. Swapping the recursion order produces a mirrored sequence that may coincidentally match a mirrored counterpart and give a wrong true.
• Adding a separate length check before comparing lists — leaves1 == leaves2 already handles unequal lengths correctly; an upfront len comparison adds noise without changing the result.

Related Problems

• same-tree — compare two trees for complete structural and value equality using the same two-tree DFS pattern
• symmetric-tree — check if a single tree mirrors itself by comparing left and right subtrees recursively
• binary-tree-inorder-traversal — the same left-first DFS traversal, collecting all nodes rather than only leaves
• path-sum — another tree problem that recurses to leaves and checks a condition on arrival
• diameter-of-binary-tree — DFS where return values propagate from leaves back up the tree to compute a global property