Abstract / Summary

Return all root-to-leaf paths in a binary tree as strings separated by arrows.

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

Typical patterns to solve this problem:

• Backtracking
• Binary Tree
• Depth First Search
• String
• 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 that generates all root-to-leaf paths of a binary tree in the form of strings separated by "->". The core logic is split between a helper method deeper that performs a depth-first traversal and accumulates node values, and the public method binaryTreePaths that prepares the traversal, invokes the helper, and formats the collected paths.

Recursive Traversal

The deeper method is the engine of the depth-first search. It receives a tree node root and a list track that represents the path taken from the root of the tree to the current node. The first conditional checks whether the current node is None; if so, the recursion terminates immediately, preventing any further processing of a missing subtree.

if not root:
    return

When a valid node is present, a new list next is created by appending the node’s value to the existing track. This copy-on-write approach ensures that each recursive branch works with its own path list, avoiding unintended side effects between sibling branches.

next = track + [ root.val ]

The method then distinguishes leaf nodes from internal nodes. A leaf is identified by the absence of both left and right children. In that case, the completed path next is stored in the instance variable self.all.

if not root.left and not root.right:
    self.all.append(next)

If the node is not a leaf, the recursion proceeds to explore the left and right subtrees, passing the updated path list next to each call.

self.deeper(root.left,  next)
self.deeper(root.right, next)

Path Collection

The public method binaryTreePaths initializes the container self.all as an empty list before starting the traversal. By resetting this attribute at the start of each call, the method guarantees that results from previous invocations do not leak into the current computation.

self.all = []
self.deeper(root, [])

After the recursive exploration finishes, self.all holds a list of lists, where each inner list contains the integer values of a root-to-leaf path in order.

Result Construction

The final phase transforms the numeric paths into the required string representation. An empty list result is created, and a loop iterates over each path stored in self.all. For each path a, a generator expression converts each integer b to a string, and "->".join concatenates them with the arrow delimiter. The resulting string is appended to result.

result = []
for a in self.all:
    result.append("->".join(str(b) for b in a))
return result

The method returns result, which contains all root-to-leaf paths formatted as specified.

Edge Cases

The implementation gracefully handles an empty tree. When root is None, the initial call to deeper returns immediately, leaving self.all empty. Consequently, the loop that builds result does not execute, and the method returns an empty list, which correctly represents the absence of any paths.

Leaf nodes that have only one child are also correctly processed. The check for a leaf (not root.left and not root.right) ensures that a node with a single child is not mistakenly treated as a terminal point; the recursion continues down the existing child, and the path is only recorded when a true leaf is reached.

The use of track + [ root.val ] creates a fresh list for each recursive call, preventing the accidental sharing of mutable state between different branches. This design choice eliminates bugs that could arise from mutating a shared list while traversing multiple branches simultaneously.

Performance Optimizations

The algorithm leverages a depth-first search that visits each node exactly once, building paths incrementally without revisiting nodes. By constructing a new list for each recursive step rather than modifying a single shared list, the code avoids the overhead of backtracking operations such as pop, which would be required if a mutable list were reused. This approach simplifies the control flow and reduces the chance of errors related to list state management.

Storing intermediate paths in self.all as lists of integers, rather than as strings, defers the string concatenation cost until after the traversal is complete. This separation means that the recursive phase focuses solely on tree navigation and path accumulation, while the formatting phase handles the relatively inexpensive conversion to strings in a single pass.

Overall, the implementation balances clarity and efficiency by isolating traversal logic from formatting, using immutable path extensions to avoid side effects, and minimizing work inside the recursive calls.

Imagine a tree standing upside down with its roots at the top and many branches growing downward. Each branch ends at a little spot called a leaf. This code acts like a tiny explorer wandering through that tree.

The explorer starts at the very top and travels down the branches one by one. Every time the explorer visits a spot, it remembers the path taken by writing down the name of the spot in a notebook.

When the explorer reaches a leaf, which is a spot where no more branches grow, it knows the journey for that path is finished. The explorer carefully saves that whole path of names into a collection.

After exploring every single branch, the explorer looks at the notebook full of paths. It goes through each path, ties the names together with little arrows, and creates a neat list of all the journeys that reached the very end of the tree.

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