Abstract / Summary

Given a binary tree return the order of values visited in left root right sequence

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

Typical patterns to solve this problem:

• Binary Tree
• Depth First Search
• Stack
• 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 performs an inorder traversal of a binary tree and returns the visited node values in a vector<int>. The algorithm follows the classic recursive pattern: traverse the left subtree, visit the current node, then traverse the right subtree. The function is expressed entirely in terms of standard library containers and relies on C++’s return-value optimization to keep the code concise.

Base Case Handling

The first logical step checks whether the supplied root pointer is null. When the tree (or a subtree) is empty, the function immediately returns an empty vector, which serves as the termination condition for the recursion.

if (!root)
    return {};

This guard ensures that leaf nodes, whose children are null, produce empty vectors for their left and right sub-calls, allowing the algorithm to correctly assemble the final result without additional conditional logic.

Recursive Descent

For a non-null node, the function recursively obtains the inorder sequences of the left and right subtrees. The calls are made directly on the child pointers, and the results are stored in local variables l and r.

auto l = inorderTraversal(root->left);
auto r = inorderTraversal(root->right);

These two lines embody the depth-first nature of the traversal. Each recursive invocation works on a smaller portion of the tree, eventually reaching the base case.

Merging Results

After acquiring the left and right sequences, the algorithm constructs the final vector for the current subtree. It begins by copying the left sequence into a new vector, appends the current node’s value, and then concatenates the right sequence.

vector<int> result(l.begin(), l.end());
result.push_back(root->val);
result.insert(result.end(), r.begin(), r.end());

The use of the range constructor vector<int>(l.begin(), l.end()) creates the result vector with the exact size needed for the left part, avoiding an intermediate default construction followed by a bulk copy. The subsequent push_back adds the node’s own value in constant time. Finally, insert appends the right sequence in a single operation, which internally copies the elements in a contiguous block.

Return Path

The assembled result vector is returned to the caller. Because the function returns by value, C++’s return-value optimization (RVO) or move semantics typically eliminate unnecessary copying, allowing the vector’s internal buffer to be transferred efficiently up the call stack.

return result;

Edge Cases Addressed

The implementation gracefully handles several edge conditions without extra code. When the tree consists of a single node, both recursive calls return empty vectors, and the final result contains only that node’s value. For highly unbalanced trees (e.g., a chain of left children), the recursion proceeds down to the deepest leaf, each level returning an empty right vector, and the left vectors are concatenated correctly. The null-pointer check at the start guarantees that even an entirely empty tree yields an empty vector rather than causing undefined behavior.

Implicit Performance Optimizations

Although the algorithm is straightforward, it benefits from a few subtle performance considerations. The range constructor for result allocates exactly enough memory for the left subtree’s elements, reducing the number of reallocations that would occur with repeated push_back calls. The insert operation for the right subtree copies its elements in bulk, which is more efficient than appending each element individually. Moreover, the function’s return by value leverages compiler optimizations such as RVO and move semantics, allowing the constructed vector to be transferred to the caller without a deep copy of its contents. These choices keep the runtime overhead low while preserving readability.

Summary of Execution Flow

The function begins by checking for a null root. If the root exists, it recursively gathers inorder vectors from the left and right children. It then builds a new vector by copying the left vector, appending the current node’s value, and inserting the right vector. The completed vector is returned, with compiler optimizations ensuring that the data movement between recursive frames is efficient. This design yields a clean, recursive solution that correctly handles empty trees, single-node trees, and arbitrarily shaped binary trees.

Imagine a big tree made of numbers where every spot can hold a little treasure. To read all the numbers in the right order, the code starts by looking at the whole tree as a smaller puzzle. It visits the left side of the tree first to find all the treasures tucked away there. Then, it looks at the middle, which is the current spot, and puts that number in a special bag. After that, it travels over to the right side of the tree to gather all the treasures hidden there. By doing this over and over, the code carefully collects every single piece of information in the perfect sequence from left to right. It is a way of walking through the branches to make sure nothing gets left behind.

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

Time: polynomial
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	AdelDaniel											Dart
	aylei					Rust
	begeekmyfriend				C
	BigEggStudy						C#
	black-shadows	C++
	bujosa					Rust
	charles-wangkai			Java
	chenyanzhe	C++
	Dijkstra-Edu			Java
	DimitrisJim				C
	everthis							JS
	fartem									Ruby
	FelixFan1122						C#
	fengvyi	C++
	gaosq0604		Python
	Garvit244		Python
	gouthampradhan			Java
	halfrost								Go
	haoel	C++
	JoshCrozier							JS
	keineahnung2345	C++
	Krazune	C++
	lennylxx				C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	muhammadfarhankt								Go
	pruthvikp		Python
	qiyuangong		Python
	ruoru					Rust
	shreymehul						C#
	sonugiri1043	C++
	suxrobGM			Java
	trung-hn		Python
	varunu28			Java
	vli02				C
	vthwang			Java
	wisdompeak	C++
	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
AdelDaniel	Dart
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Rust
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
muhammadfarhankt	Go
pruthvikp	Python
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	Java
trung-hn	Python
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
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