Abstract / Summary

Swap the left and right children of each node in a binary tree recursively.

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 80% (3+ 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 method to invert a binary tree in place. It follows a classic depth-first recursion pattern: for each node it swaps its left and right subtrees, then recursively processes the newly positioned children. The algorithm terminates when it reaches a null pointer, which represents an empty subtree. By operating directly on the input nodes, the solution avoids allocating auxiliary structures and returns the original root pointer after transformation.

Base-case handling

The first conditional checks whether the current node reference is null. This guard captures the situation where the tree is empty or a leaf’s child is missing, and it returns the null pointer unchanged.

if (!root)
    return root;

When the input tree has no nodes, the function exits immediately, preserving the null result. For leaf nodes, the recursive calls later encounter null pointers, and this check prevents further descent.

Swapping child pointers

The core transformation is performed by a single call to swap, which exchanges the left and right child pointers of the current node.

swap(root->left, root->right);

Using std::swap (or the equivalent built-in overload) swaps the pointers in constant time without allocating temporary nodes. This in-place modification is the primary optimization that keeps memory usage minimal.

Recursive descent

After the children are swapped, the method recurses on both subtrees. Because the pointers have already been exchanged, the recursive calls naturally continue the inversion down the tree.

invertTree(root->left);
invertTree(root->right);

Each recursive invocation follows the same pattern: base-case check, pointer swap, and further recursion. The recursion depth matches the height of the tree, ensuring that each node is visited exactly once.

Return value

The function concludes by returning the original root pointer, now representing the root of the inverted tree.

return root;

Returning the root enables callers to receive the transformed tree directly, facilitating chaining or immediate use of the result.

Edge-case considerations

The implementation gracefully handles several edge conditions:

• Empty tree - The initial null check returns immediately, leaving the result as a null pointer.
• Single-node tree - The swap operation exchanges two null child pointers, which is a no-op, and the recursive calls hit the base case, leaving the solitary node unchanged.
• Highly unbalanced tree - Even when one side of the tree is significantly deeper, the recursion proceeds correctly because each call checks for null before proceeding, preventing dereferencing of invalid pointers.

Performance characteristics

The algorithm achieves in-place inversion with no auxiliary containers, which minimizes heap allocations and reduces pressure on the memory allocator. The pointer swap is a constant-time operation, and each node is processed exactly once, leading to linear work relative to the number of nodes. The recursion stack depth is bounded by the tree height, which is optimal for a depth-first traversal without explicit stack management. The use of swap leverages move semantics for pointer types, ensuring that the exchange incurs only a few machine instructions. Overall, the implementation delivers an efficient solution with low overhead.

Imagine you have a drawing of a tree made of branches, where every branch has a left side and a right side. This code is like a magical mirror that runs through the tree to flip everything around.

First, it checks if the tree is empty. If there is nothing there, it just stops. If there is a branch, it takes the left part and the right part and swaps them, just like switching the spots where you keep your left and right shoes.

After swapping the parts at the top, the code keeps moving down to the next branches. It performs this same game of swapping on the left side and then on the right side over and over again. It keeps going deeper until it has visited every single part of the tree, swapping their sides as it goes. By the time it finishes, the entire tree looks like a mirror reflection of how it started.

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