#872

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Leaf-Similar Trees

Determine if two binary trees have identical leaf sequences using efficient traversal and state tracking techniques.

Problem Statement

Given two binary trees, define a leaf value sequence as the list of values of all leaf nodes visited from left to right. Two trees are leaf-similar if their leaf value sequences are identical.

Implement a function that, given the roots of two binary trees, returns true if they are leaf-similar and false otherwise. Optimize for traversal efficiency while maintaining the correct order of leaf nodes.

Examples

Example 1

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

Example details omitted.

Example 2

Input: root1 = [1,2,3], root2 = [1,3,2]

Output: false

Example details omitted.

Constraints

The number of nodes in each tree will be in the range [1, 200].
Both of the given trees will have values in the range [0, 200].

Solution Approach

Collect leaf sequences via DFS

Traverse each tree using depth-first search. Whenever a leaf node is reached, append its value to a sequence list. Maintain the left-to-right order to ensure correct comparison.

Compare sequences directly

After generating both leaf sequences, compare them element by element. If all elements match and lengths are equal, the trees are leaf-similar; otherwise, they are not.

Optimize traversal and storage

Use a single pass DFS for each tree and store leaves in arrays. This ensures O(N + M) time and space complexity, where N and M are the number of nodes in each tree.

Complexity Analysis

Metric	Value
Time	O(N + M)
Space	O(N + M)

The algorithm visits every node once to collect leaf values, resulting in O(N + M) time. Leaf sequences are stored in arrays, giving O(N + M) space usage.

What Interviewers Usually Probe

Asks about leaf order preservation in DFS traversal.
Checks if candidate handles trees of different shapes with identical leaf sequences.
Probes for optimization beyond naïve full-tree comparison.

Common Pitfalls or Variants

Common pitfalls

Ignoring the left-to-right order of leaves leading to incorrect sequence comparison.
Mistaking internal nodes for leaves during sequence collection.
Assuming trees of different structures cannot be leaf-similar.

Follow-up variants

Compare leaf sequences using iterative DFS instead of recursion.
Handle N-ary trees or trees with more than two children per node.
Return the matching leaf sequence if trees are leaf-similar instead of a boolean.

FAQ

What does leaf-similar mean in the context of trees?

Leaf-similar means that two trees have identical sequences of leaf values from left to right.

Which traversal is best to collect leaf sequences?

Depth-First Search (DFS) is preferred to collect leaves in left-to-right order efficiently.

Can leaf-similar trees have different structures?

Yes, trees can have different internal structures but still be leaf-similar if their leaf sequences match.

What is the time complexity for checking leaf similarity?

It is O(N + M), where N and M are the numbers of nodes in the two trees.

How does GhostInterview help with Leaf-Similar Trees problem?

GhostInterview automates leaf sequence extraction, ensures proper DFS traversal, and flags mismatches efficiently.

terminal

Solution

Solution 1: DFS

We can use Depth-First Search (DFS) to traverse the leaf nodes of the two trees, storing the values of the leaf nodes in two lists $l_1$ and $l_2$ respectively. Finally, we compare whether the two lists are equal.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

# 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 dfs(root: Optional[TreeNode], nums: List[int]) -> None:
            if root.left == root.right:
                nums.append(root.val)
                return
            if root.left:
                dfs(root.left, nums)
            if root.right:
                dfs(root.right, nums)

        l1, l2 = [], []
        dfs(root1, l1)
        dfs(root2, l2)
        return l1 == l2

Continue Practicing

#865 smallest subtree with all the deepest nodes #863 all nodes distance k in binary tree #897 increasing order search tree