Abstract / Summary

Check if two trees have the same sequence of leaf values when read left to right

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 70% (900k+ submissions).

Typical patterns to solve this problem:

• Binary Tree
• Depth First Search
• Tree

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a single public method leafSimilar. The method determines whether two binary trees produce identical sequences of leaf node values when traversed from left to right. The core logic is encapsulated in a nested helper function leafs that recursively extracts leaf values from a given subtree and returns them as a list. The final comparison uses Python’s equality operator on the two resulting lists.

Core Logic

Public Method

def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
    def leafs(node):
        if not node:
            return []
        if not node.left and not node.right:
            return [ node.val ]
        return leafs(node.left) + leafs(node.right)

    return leafs(root1) == leafs(root2)

The method receives two root references, root1 and root2. It defines the helper leafs and then directly returns the boolean result of comparing the two leaf sequences.

Helper Function

def leafs(node):
    if not node:
        return []
    if not node.left and not node.right:
        return [ node.val ]
    return leafs(node.left) + leafs(node.right)

The helper follows a depth-first traversal pattern:

• When the current node is None, it yields an empty list, representing the absence of leaves in that branch.
• When the node has no left or right child, it is identified as a leaf and its value is wrapped in a single-element list.
• For internal nodes, the function recursively gathers leaf lists from the left subtree and the right subtree, concatenating them to preserve left-to-right order.

Edge Cases Handled

The recursion explicitly checks for a None node, which covers the scenario where one or both input trees are empty. In such a case, leafs returns an empty list, and the equality comparison correctly evaluates whether both trees lack leaves.

A tree consisting of a single node is also addressed. The node satisfies the “no left and no right child” condition, causing the function to return a list containing that single value. The comparison then reflects whether both trees consist of the same solitary leaf.

When one tree is deeper than the other but shares the same leaf values in the same order, the concatenation of leaf lists from each subtree ensures that only leaf nodes contribute to the final sequence, effectively ignoring structural differences that do not affect leaf ordering.

Performance Characteristics

The algorithm leverages recursion to traverse each tree exactly once, visiting every node to determine leaf status. By returning lists of leaf values and concatenating them, the implementation builds the final leaf sequence without allocating auxiliary containers for intermediate traversal state beyond the call stack. This approach keeps the memory footprint proportional to the depth of the tree plus the size of the leaf list, avoiding the need for explicit queues or stacks.

The use of Python’s list concatenation (+) naturally preserves the left-to-right ordering of leaves, which is essential for a correct comparison. Because the concatenation occurs only at the point where a subtree’s leaf list is fully constructed, the operation does not interfere with the logical flow of the recursion and benefits from Python’s efficient handling of list objects.

Overall, the design provides a clear and direct mapping from tree structure to leaf sequence, delivering the required result with minimal overhead beyond the inherent recursion.

Imagine a big family tree, kind of like the ones you might draw with branches going everywhere. Some branches end in a little leaf, and those are the only parts we care about today. The code starts by looking at a tree and walking along every single branch until it finds the leaves. It collects all those little leaves into a row, just like picking apples from a tree and putting them in a basket. Then the code does the exact same thing for a second tree and fills a second basket. Once both baskets are full of leaves, the code looks at them side by side. If the leaves in the first basket are in the same order as the leaves in the second basket, the code says that the two trees are similar friends.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java								TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java	Go		Rust			JS
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	BigEggStudy					C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai			Java
	DimitrisJim										C
	fartem							Ruby
	fengvyi	C++
	fsq	C++
	gouthampradhan			Java
	halfrost				Go
	JoshCrozier									JS
	keineahnung2345	C++
	Krazune	C++
	lkwq007		Python
	lzl124631x	C++
	muhammadfarhankt				Go
	pruthvikp		Python
	qiyuangong			Java
	ruoru						Rust
	suxrobGM					C#
	trung-hn		Python
	varunu28			Java
	vthwang			Java
	yuanliu666								Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
DimitrisJim	C
fartem	Ruby
fengvyi	C++
fsq	C++
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lkwq007	Python
lzl124631x	C++
muhammadfarhankt	Go
pruthvikp	Python
qiyuangong	Java
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
yuanliu666	Kotlin
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality