Domain 1EasyCORE

Leaf-Similar Trees

The problem asks us to determine if two binary trees are leaf-similar. Two trees are considered leaf-similar if their leaf value sequences (the values of the leaves from left to right) are identical.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree#Depth-first Search

872. Leaf-Similar Trees

Model: qwen2.5-coder:14b
Topics: Tree,Depth-first Search
FAANG asked: 1
Acceptance rate: 64.5%


Problem Breakdown

The problem asks us to determine if two binary trees are leaf-similar. Two trees are considered leaf-similar if their leaf value sequences (the values of the leaves from left to right) are identical.

Inputs:

  • Two binary tree root nodes, root1 and root2.

Outputs:

  • A boolean value indicating whether the two trees are leaf-similar.

Implicit Constraints or Tricky Edge Cases:

  • The trees can be empty (though the problem guarantees at least one node).
  • The values of the nodes are in the range [0, 200].
  • The number of nodes in each tree is between 1 and 200.

Intuition

A brute-force approach would involve collecting all leaf nodes from both trees and then comparing their sequences. This approach has a time complexity of O(n) where n is the total number of nodes, but it requires additional space to store the leaf sequences.

The key insight is that we can compare the leaf sequences on-the-fly without storing them entirely in memory. We can use a depth-first search (DFS) to traverse both trees simultaneously and compare their leaves as soon as they are found. This approach reduces the space complexity by avoiding the need for additional storage for the leaf sequences.

Approach

  1. Depth-First Search (DFS): Use DFS to traverse each tree and collect the leaf values.
  2. Simultaneous Comparison: As we traverse both trees, compare their leaves one by one. If at any point a mismatch is found, return false.
  3. Complete Traversal Check: Ensure that both trees are fully traversed before concluding they are leaf-similar.

Complexity Analysis

  • Time Complexity: O(n) where n is the total number of nodes in both trees combined. We visit each node exactly once.
  • Space Complexity: O(h) where h is the height of the tree, due to the recursion stack. In the worst case (completely unbalanced tree), this could be O(n).

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def leafSimilar(root1: TreeNode, root2: TreeNode) -> bool:
    def get_leaf_sequence(node):
        if not node:
            return
        if not node.left and not node.right:
            yield node.val
        yield from get_leaf_sequence(node.left)
        yield from get_leaf_sequence(node.right)

    seq1 = get_leaf_sequence(root1)
    seq2 = get_leaf_sequence(root2)

    while True:
        leaf1 = next(seq1, None)
        leaf2 = next(seq2, None)
        if leaf1 != leaf2:
            return False
        if leaf1 is None and leaf2 is None:
            return True

Edge Cases Handled

  • Single Node Trees: If both trees have only one node with the same value, they are leaf-similar.
  • Different Number of Leaves: If one tree has more leaves than the other, the sequences will differ at some point, and the function will return false.
  • Empty Trees: The problem guarantees that each tree has at least one node, so this case is not applicable here.