Is Leaf-Similar Trees easy or hard?

Leaf-Similar Trees is categorized as an Easy problem. The main requirement is recognizing leaf nodes and performing a simple DFS traversal while preserving left-to-right ordering.

Leaf-Similar Trees Python/Java solution

Python and Java solutions both implement DFS traversal. Python often uses recursion to append leaf values to a list, while Java may use either recursion or an explicit stack for iterative DFS. Both approaches run in O(n + m) time.

How to solve Leaf-Similar Trees in O(n)?

Run DFS on each tree to extract leaf nodes in left-to-right order. Store the leaf values in arrays and compare the arrays at the end. Since every node is processed once, the total runtime remains linear in the number of nodes.

What is the best approach for Leaf-Similar Trees?

Recursive depth-first search (DFS) is the most common approach. Traverse each tree, record values of nodes that have no children, and compare the two leaf sequences. The traversal visits each node once, giving O(n + m) time complexity.

Is Leaf-Similar Trees asked at Google/Amazon/Meta?

Leaf-Similar Trees represents a typical easy-level binary tree traversal question. Variants of leaf traversal and DFS-based comparisons appear in interviews at companies like Amazon and Google to test tree fundamentals and recursion.

What data structure is used in Leaf-Similar Trees?

The problem uses a binary tree as the core data structure. Depth-first search is used to traverse the tree, and either recursion stacks or an explicit stack structure helps maintain traversal state while collecting leaf nodes.

What is the time complexity of Leaf-Similar Trees?

The time complexity is O(n + m), where n and m are the number of nodes in the two binary trees. Each node is visited exactly once during DFS traversal. Comparing the two leaf sequences takes linear time relative to the number of leaves.

Description Solution Video 7:04

872. Leaf-Similar Trees

Easy70.0% acceptance5 companies

Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

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 2:

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

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].

Asked at 5 companies

Snowflake

Google Amazon Microsoft Meta

Topics

7:04

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
9        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[3,5,1,6,2,9,8,null,null,7,4]
[3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]

Input

[1,2,3]
[1,3,2]

Your code is saved on this device.Solution