Leaf-Similar Trees

Problem in plain words

Read the leaves of a binary tree from left to right and you get a list of values — call it the tree's leaf sequence. Given two trees, return true if their leaf sequences are exactly the same list (same values, same order), and false otherwise. The inner shape of the trees does not matter.

For instance, a tree 1 with children 2 and 3 has leaf sequence [2, 3]. A completely different tree 9 whose left child 7 has children 2 and 3 also has leaf sequence [2, 3], so the two are leaf-similar.

Intuition

Any depth-first traversal that always explores the left child before the right child visits the leaves in left-to-right order. So we only need a DFS that records a node when it has no children. Run it on both trees and compare the resulting lists.

Approach

1. Write a helper that walks a tree depth-first, left subtree before right subtree.
2. Whenever the current node has neither a left nor a right child, append its value to a list.
3. Build the leaf list for root1 and for root2.
4. Return whether the two lists are equal (same length and same values in order).

Dry run

Tree A: 1 → 2, 3. Tree B: 9 → left 7 (children 2, 3), right missing.

Java solution

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> first = new ArrayList<>();
        List<Integer> second = new ArrayList<>();
        collect(root1, first);
        collect(root2, second);
        return first.equals(second);
    }

    private void collect(TreeNode node, List<Integer> leaves) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) {
            leaves.add(node.val);
            return;
        }
        collect(node.left, leaves);
        collect(node.right, leaves);
    }
}

Python solution

class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def leaves(root):
            out, stack = [], [root]
            while stack:
                node = stack.pop()
                if node is None:
                    continue
                if node.left is None and node.right is None:
                    out.append(node.val)
                else:
                    # push right first so the left child is processed first
                    stack.append(node.right)
                    stack.append(node.left)
            return out

        return leaves(root1) == leaves(root2)

Complexity

Edge cases and common mistakes

• Recording internal nodes — only nodes with zero children are leaves. A node with just one child is not a leaf.
• Wrong push order in an iterative DFS — with a stack, push the right child before the left so the left one pops first.
• Comparing with `==` on Java lists — that compares references. Use List.equals, which compares element by element.
• Different leaf counts — the list comparison already returns false when the lengths differ, no special case needed.