Abstract / Summary

Check if a binary tree is a mirror of itself around its center vertical axis.

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 62% (4+ million submissions).

Typical patterns to solve this problem:

• Binary Tree
• Breadth First Search
• 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 Solution class with a method isSymmetric that determines whether a binary tree is symmetric around its center. The algorithm relies on a recursive helper function named same that simultaneously traverses the left and right subtrees, comparing node values and structure in a mirrored fashion.

Core Logic

The entry point of the algorithm is the call to same with the left and right children of the root node:

return same(root.left, root.right)

The helper function same embodies the core comparison logic:

def same(left, right):
    if not left and not right:
        return True
    if not left or  not right:
        return False

    if left.val != right.val:
        return False

    return same(left.left, right.right) and same(left.right, right.left)

The function first checks for the simultaneous absence of both nodes, which indicates that the current pair of positions is symmetric. If only one of the nodes is missing, symmetry is broken and the function returns False. When both nodes exist, their values are compared; a mismatch leads to an immediate False. If the values match, the function proceeds to recursively compare the outer pair (left.left with right.right) and the inner pair (left.right with right.left). The logical and ensures that both mirrored sub-structures must be symmetric for the overall result to be True.

Edge Cases

The recursion explicitly handles the scenario where the tree is empty. In that case, root.left and root.right are both None, causing the first condition in same to evaluate to True, and the method returns True, correctly identifying an empty tree as symmetric.

When the tree consists of a single node, both root.left and root.right are None. The same base case applies, and the method returns True, reflecting that a single-node tree is symmetric by definition.

The function also gracefully manages trees with uneven depths. If at any depth one subtree terminates earlier than its mirror, the second conditional (if not left or not right) captures the asymmetry and returns False without further recursion.

Performance Considerations

The algorithm leverages depth-first recursion, visiting each node exactly once while performing constant-time operations at each step (value comparison and pointer checks). By returning early on mismatches or structural differences, the recursion avoids unnecessary traversal of subtrees that are already known to be asymmetric, which reduces the total number of recursive calls in non-symmetric cases.

The use of short-circuit evaluation in the final return statement (same(left.left, right.right) and same(left.right, right.left)) ensures that if the outer pair fails the symmetry test, the inner pair is not evaluated, providing an additional optimization for early termination.

Imagine a tree made of branches that mirror each other like looking into a magical mirror. The code starts by looking at the very top of the tree and splitting it into two paths, one on the left and one on the right.

To see if both sides are perfect twins, the computer compares the pieces one by one. It checks if both sides are empty at the same time, because two empty spots are perfectly matching. If one side has a branch while the other side is empty, then they are not twins. Next, it looks at the little value tags on each branch. If the tags are different numbers, the sides are not the same.

If the tags match, the computer continues the game. It looks at the far left piece and the far right piece, and then it looks at the inner pieces that are crisscrossed. It repeats this pattern for every single branch all the way down the tree. If every single piece finds a matching twin on the other side, the whole tree is symmetric.

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

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

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		Rust		JS			Go	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei					Rust
	begeekmyfriend				C
	BigEggStudy						C#
	black-shadows	C++
	bujosa					Rust
	charles-wangkai			Java
	chenyanzhe	C++
	DimitrisJim				C
	everthis							JS
	fartem								Ruby
	FelixFan1122						C#
	fengvyi	C++
	gaosq0604		Python
	Garvit244		Python
	gouthampradhan			Java
	halfrost										Go
	haoel	C++
	JoshCrozier							JS
	Krazune	C++
	lennylxx				C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	pruthvikp		Python
	qiyuangong		Python
	ruoru					Rust
	shreymehul						C#
	sonugiri1043	C++
	suxrobGM			Java
	varunu28			Java
	vli02				C
	vthwang			Java
	XiaotaoGuo	C++
	yuanliu666									Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Rust
charles-wangkai	Java
chenyanzhe	C++
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
Krazune	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
pruthvikp	Python
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	Java
varunu28	Java
vli02	C
vthwang	Java
XiaotaoGuo	C++
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