Problem Description

You are given two binary trees and need to determine if they are "leaf-similar". Two binary trees are considered leaf-similar when their leaf value sequences are identical.

A leaf value sequence is formed by collecting all the leaf node values from a binary tree in left-to-right order. A leaf node is a node that has no children (both left and right children are null).

For example, if a binary tree has leaf nodes with values 6, 7, 4, 9, 8 when traversed from left to right, then its leaf value sequence is (6, 7, 4, 9, 8).

Your task is to:

1. Find the leaf value sequence of the first tree (root1)
2. Find the leaf value sequence of the second tree (root2)
3. Compare these sequences and return true if they are exactly the same, false otherwise

The solution uses a depth-first search (DFS) approach to traverse each tree and collect leaf values. The helper function dfs recursively explores the tree:

• When it encounters a leaf node (identified by root.left == root.right, meaning both children are None), it adds the node's value to the list
• Otherwise, it recursively traverses the left subtree (if it exists) and then the right subtree (if it exists)

After collecting leaf sequences l1 and l2 from both trees, the solution simply compares these lists for equality using l1 == l2.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: Although this is specifically a binary tree problem, a tree is a special type of graph (an acyclic connected graph). Binary trees are graphs with specific properties where each node has at most two children.

Is it a tree?

• Yes: The problem explicitly deals with binary trees. We need to traverse two binary trees and compare their leaf node sequences.

DFS

• Yes: This is our conclusion. For tree problems, DFS is a natural choice, especially when we need to:
  • Traverse all nodes in the tree
  • Reach leaf nodes (nodes at the deepest level)
  • Process nodes in a specific order (left-to-right for leaves)

Conclusion: The flowchart suggests using DFS (Depth-First Search) for this tree traversal problem.

The DFS pattern is ideal here because:

1. We need to explore each path from root to leaf completely before moving to the next path
2. DFS naturally visits leaves in left-to-right order when we process left subtrees before right subtrees
3. The recursive nature of DFS matches the recursive structure of trees perfectly
4. We can easily identify and collect leaf nodes during the traversal when we encounter nodes with no children

Intuition

When we need to compare if two trees have the same leaf sequence, the key insight is that we need to extract and compare just the leaf nodes from each tree, ignoring their internal structure.

Think of it like comparing two family trees - we only care if they have the same descendants at the bottom generation, not how the family branches are arranged. The internal nodes (non-leaf nodes) and the tree structure don't matter; only the left-to-right order of leaves matters.

To collect leaves in left-to-right order, we need a traversal strategy that:

1. Visits every node to find all leaves
2. Maintains the left-to-right ordering

DFS is perfect for this because when we recursively visit the left subtree before the right subtree, we naturally encounter leaves in left-to-right order. It's like reading a book - we go deep into the left side first, record any leaves we find, then move to the right.

The elegant observation in the solution is identifying a leaf node: a node is a leaf when root.left == root.right (both are None). This is a concise way of saying "this node has no children."

Once we have both leaf sequences, comparing them is straightforward - just check if the two lists are equal. If l1 == l2, the trees are leaf-similar.

The beauty of this approach is its simplicity: instead of trying to compare trees structurally while traversing, we separate the problem into two independent steps:

1. Extract leaf sequences from each tree
2. Compare the sequences

This decomposition makes the solution clean and easy to understand.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The solution implements a DFS traversal to collect leaf values from both trees, then compares the resulting sequences.

Implementation Details:

1. Helper Function Design: We create a dfs helper function that takes two parameters:

   • root: The current node being visited
   • nums: A list that accumulates leaf values during traversal

2. Leaf Node Detection: The key insight is the condition root.left == root.right. This checks if both children are None (since None == None is True), elegantly identifying leaf nodes without explicitly checking root.left is None and root.right is None.

3. DFS Traversal Pattern: The function follows a standard recursive DFS pattern:

   if root.left:
       dfs(root.left, nums)
   if root.right:
       dfs(root.right, nums)

   By visiting the left subtree before the right subtree, we ensure leaves are collected in left-to-right order.

4. List as Accumulator: We use Python lists l1 and l2 to accumulate leaf values. The lists are passed by reference to the recursive function, so all recursive calls append to the same list.

5. Main Logic Flow:

   • Initialize two empty lists: l1 = [] and l2 = []
   • Call dfs(root1, l1) to populate l1 with leaves from the first tree
   • Call dfs(root2, l2) to populate l2 with leaves from the second tree
   • Return l1 == l2 to check if the sequences are identical

Time Complexity: O(n + m) where n and m are the number of nodes in the two trees respectively. We visit each node exactly once.

Space Complexity: O(h1 + h2) for the recursive call stack (where h1 and h2 are the heights of the trees), plus O(l1 + l2) for storing the leaf values (where l1 and l2 are the number of leaves in each tree).

Example Walkthrough

Let's walk through the solution with two small binary trees to see how the algorithm determines if they're leaf-similar.

Example Trees:

Tree 1:        Tree 2:
    3              5
   / \            / \
  5   1          6   1
 / \              \
6   2              2

Step 1: Extract leaves from Tree 1

Starting with root1 (value 3), we call dfs(root1, l1) where l1 = []:

1. At node 3: Not a leaf (has children), so traverse left to node 5
2. At node 5: Not a leaf (has children), so traverse left to node 6
3. At node 6: This is a leaf! (left == right == None), add 6 to l1: l1 = [6]
4. Back to node 5, traverse right to node 2
5. At node 2: This is a leaf! Add 2 to l1: l1 = [6, 2]
6. Back to node 3, traverse right to node 1
7. At node 1: This is a leaf! Add 1 to l1: l1 = [6, 2, 1]

Step 2: Extract leaves from Tree 2

Starting with root2 (value 5), we call dfs(root2, l2) where l2 = []:

1. At node 5: Not a leaf (has children), so traverse left to node 6
2. At node 6: This is a leaf! Add 6 to l2: l2 = [6]
3. Back to node 5, traverse right to node 1
4. At node 1: Not a leaf (has right child), skip left, traverse right to node 2
5. At node 2: This is a leaf! Add 2 to l2: l2 = [6, 2]
6. Back to node 1: No more children to visit
7. Back to node 5: No more children to visit

Wait, we have a problem! Tree 2's leaf sequence is [6, 2], but we need to check node 1 more carefully. Node 1 has only a right child (node 2), so it's not a leaf. Let me correct the traversal:

Actually, the leaf sequence for Tree 2 is just [6, 2] because node 1 is not a leaf (it has a right child).

Step 3: Compare sequences

• Tree 1 leaf sequence: [6, 2, 1]
• Tree 2 leaf sequence: [6, 2]
• Compare: [6, 2, 1] == [6, 2] returns False

These trees are not leaf-similar because their leaf sequences differ.

Example of Leaf-Similar Trees:

Let's modify Tree 2 to make them leaf-similar:

Tree 1:        Tree 2:
    3              7
   / \            / \
  5   1          6   4
 / \            /   / \
6   2          2   1   8
                        \
                         1

For Tree 2's new structure:

• Traverse to node 7 → left to node 6 → left to node 2 (leaf): [2]
• Back to node 6 (done) → back to node 7 → right to node 4
• At node 4 → left to node 1 (leaf): [2, 1]
• Back to node 4 → right to node 8 → right to node 1 (leaf): [2, 1, 1]

Wait, this doesn't match. Let me create a simpler matching example:

Tree 1:        Tree 2:
    1              2
   / \              \
  6   2              1
                    / \
                   6   2

Tree 1 leaves: Visit left (6 is leaf), then right (2 is leaf) = [6, 2] Tree 2 leaves: Visit right to node 1, then left (6 is leaf), then right (2 is leaf) = [6, 2]

Both sequences are [6, 2], so these trees are leaf-similar despite having completely different structures!

Solution Implementation

Time and Space Complexity

Time Complexity: O(n₁ + n₂) where n₁ is the number of nodes in root1 and n₂ is the number of nodes in root2. Since in the worst case both trees could have the same number of nodes n, this simplifies to O(n). The algorithm performs a depth-first search (DFS) on both trees, visiting each node exactly once.

Space Complexity: O(h₁ + h₂ + l₁ + l₂) where h₁ and h₂ are the heights of the two trees (for the recursion call stack), and l₁ and l₂ are the number of leaf nodes in each tree (for storing the leaf values in lists). In the worst case, the height of a tree can be O(n) for a skewed tree, and the number of leaves can be up to O(n/2) for a complete binary tree. Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Leaf Order Due to Wrong Traversal

A common mistake is collecting leaves in the wrong order by not maintaining a consistent traversal pattern. Some developers might accidentally mix pre-order, in-order, or post-order traversal logic, or traverse right before left.

Incorrect Implementation:

def collect_leaves(node, leaf_values):
    if not node:
        return
    if not node.left and not node.right:
        leaf_values.append(node.val)
    # Wrong: traversing right before left
    collect_leaves(node.right, leaf_values)  
    collect_leaves(node.left, leaf_values)

Solution: Always traverse left subtree before right subtree to maintain left-to-right order:

def collect_leaves(node, leaf_values):
    if not node:
        return
    if not node.left and not node.right:
        leaf_values.append(node.val)
        return
    collect_leaves(node.left, leaf_values)   # Left first
    collect_leaves(node.right, leaf_values)  # Then right

2. Creating New Lists in Recursive Calls

A critical error is creating new lists in each recursive call instead of passing the same list by reference, resulting in lost leaf values.

Incorrect Implementation:

def collect_leaves(node):
    leaf_values = []  # Creates new list each time!
    if not node:
        return leaf_values
    if not node.left and not node.right:
        leaf_values.append(node.val)
        return leaf_values
    # These returned values are never captured
    collect_leaves(node.left)   
    collect_leaves(node.right)
    return leaf_values

Solution: Pass the list as a parameter to maintain a single accumulator:

def collect_leaves(node, leaf_values):  # Pass list as parameter
    if not node:
        return
    if not node.left and not node.right:
        leaf_values.append(node.val)
        return
    collect_leaves(node.left, leaf_values)
    collect_leaves(node.right, leaf_values)

3. Incorrectly Identifying Leaf Nodes

Some implementations fail to properly identify leaf nodes, potentially treating nodes with one child as leaves or missing actual leaves.

Incorrect Implementation:

# Wrong: This treats nodes with one null child as leaves
if not node.left or not node.right:  
    leaf_values.append(node.val)
  
# Wrong: Overly complex and error-prone
if node.left is None:
    if node.right is None:
        leaf_values.append(node.val)

Solution: Use clear and correct leaf identification:

# Correct and clear
if node.left is None and node.right is None:
    leaf_values.append(node.val)
  
# Or the elegant version from the original
if node.left == node.right:  # Both are None
    leaf_values.append(node.val)

4. Not Handling Edge Cases

Failing to handle null trees or single-node trees can cause runtime errors.

Incorrect Implementation:

def leafSimilar(self, root1, root2):
    leaves1, leaves2 = [], []
    # Doesn't check if roots are None
    self.collect_leaves(root1, leaves1)
    self.collect_leaves(root2, leaves2)
    return leaves1 == leaves2

Solution: The helper function should handle None gracefully:

def collect_leaves(node, leaf_values):
    if not node:  # Handle None nodes
        return
    # Rest of the logic...