Leaf-Similar Trees – LeetCode75 Python Solution Explained

The Leaf-Similar Trees problem (LeetCode75) is a popular binary tree challenge that tests your understanding of tree traversal, recursion, and sequence comparison. It is commonly asked in technical interviews to evaluate your problem-solving skills in working with tree data structures and handling leaf nodes efficiently.

In this blog, we will break down the problem, provide examples, explain the Python solution step by step, analyze time and space complexity and discuss real-world applications.

Problem Statement

Two binary trees are considered leaf-similar if their leaf nodes when traversed from left to right, form the same sequence.

You are given the roots of two binary trees, root1 and root2. Return True if they are leaf-similar otherwise return False.

Leaf nodes are nodes that do not have any children (no left or right).

Example 1

Input:

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

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

Output:

True

Explanation:
Leaf nodes of Tree 1 = [6, 7, 4, 9, 8]
Leaf nodes of Tree 2 = [6, 7, 4, 9, 8]
Both sequences are identical.

Example 2

Input:

Tree 1: [1,2,3]
Tree 2: [1,3,2]

Output:

False

Explanation:
Leaf sequences differ: Tree 1 leaves = [2,3], Tree 2 leaves = [3,2].

Understanding the Problem

The goal is to extract leaf nodes from both trees in left-to-right order and then compare the sequences. Key insights:

Leaf nodes are nodes with no children.
Order matters: sequences must match exactly from left to right.
Recursive traversal (DFS) is a natural approach.

Complete Python Solution

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(root, leaves):
            if root:
                if not root.left and not root.right:
                    leaves.append(root.val)
                collect_leaves(root.left, leaves)
                collect_leaves(root.right, leaves)

        leaves1, leaves2 = [], []
        collect_leaves(root1, leaves1)
        collect_leaves(root2, leaves2)
        
        return leaves1 == leaves2

Step-by-Step Explanation

Step 1: Define a Leaf Collection Function

We create a helper function collect_leaves that traverses the tree recursively and appends leaf values to a list.

def collect_leaves(root, leaves):
    if root:
        if not root.left and not root.right:  # leaf node
            leaves.append(root.val)
        collect_leaves(root.left, leaves)
        collect_leaves(root.right, leaves)

Step 2: Collect Leaf Sequences for Both Trees

Initialize two empty lists and collect leaf nodes for each tree.

leaves1, leaves2 = [], []
collect_leaves(root1, leaves1)
collect_leaves(root2, leaves2)

Step 3: Compare Leaf Sequences

After collecting the sequences, simply check if they are equal.

return leaves1 == leaves2

If sequences match, the trees are leaf-similar; otherwise, they are not.

Time and Space Complexity

Time Complexity:O(n + m)
- n = number of nodes in root1
- m = number of nodes in root2
  Each tree is traversed exactly once.
Space Complexity:O(h1 + h2)
- h1 and h2 are the heights of the two trees, accounting for recursion stack.
- Additionally, O(L1 + L2) space is used to store leaf sequences, where L1 and L2 are the number of leaf nodes.

Edge Cases

Empty Trees: Two empty trees are leaf-similar.
Single Node Trees: If both trees have a single node, they are leaf-similar if the values match.
Different Number of Leaves: Automatically returns False.

Real-World Applications

Tree Comparison in XML/JSON Structures: Compare leaf nodes in structured data.
Data Consistency Checks: Ensure two hierarchical datasets have similar terminal values.
Decision Trees Validation: Compare outcomes of machine learning trees.
Genomic or Phylogenetic Trees: Compare leaf sequences in biological datasets.

Conclusion

The Leaf-Similar Trees problem is an excellent exercise for understanding tree traversal, recursion and sequence comparison. By extracting leaf nodes and comparing sequences, you can efficiently determine similarity between binary trees.

This problem improves your understanding of:

Recursive DFS traversal
Leaf node identification
Sequence comparison in trees

Practicing this type of problem prepares you for coding interviews and real-world applications in data analysis and hierarchical structures.