Abstract / Summary

Build a string from a binary tree using preorder traversal with parentheses to show structure and null nodes.

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 71% (500k+ submissions).

Typical patterns to solve this problem:

• 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 converts a binary tree into a parenthesized string representation that follows a specific preorder format. The algorithm walks the tree recursively, emitting the node value and surrounding sub-expressions with parentheses only when required by the presence of children. The design deliberately treats the empty tree as an empty string, which aligns with the contract of the method.

Core Logic

The entry point checks for a null root and returns an empty string immediately. This guard clause eliminates unnecessary processing for the base case of an empty tree.

if not root:
    return ""

When a node exists, its integer value is converted to a string and stored as the initial part of the result.

result = str(root.val)

The next decision point determines whether the left subtree should be represented. The condition root.left or root.right captures two scenarios: a genuine left child, or the need to emit an empty pair of parentheses when a right child exists but the left child is absent. In both cases the method recurses on root.left and wraps the returned string with parentheses.

if root.left or root.right:
    result += "(" + self.tree2str(root.left) + ")"

Finally, the right subtree is processed only when it exists. The presence of a right child always warrants a pair of parentheses, regardless of the left subtree’s state.

if root.right:
    result += "(" + self.tree2str(root.right) + ")"

The assembled string is then returned to the caller.

return result

Edge-Case Handling

The recursion naturally accommodates several edge conditions:

• Empty tree - The initial guard returns an empty string, satisfying the specification for a null input.
• Leaf node - When both children are absent, the condition root.left or root.right evaluates to false, so no parentheses are added. The output consists solely of the node’s value.
• Node with only a right child - The left-child check fails, but the right-child block executes. Because the left side is omitted, the algorithm inserts an empty pair of parentheses for the missing left child, preserving the required format value()(right).
• Node with only a left child - The left-child block runs, adding the left subtree inside parentheses. The right-child block is skipped, yielding value(left) without an extra empty pair.

These conditions ensure that the generated string uniquely represents the original tree structure.

Performance Characteristics

The solution leverages depth-first recursion, which means each node is visited exactly once. By constructing the result string incrementally through concatenation, the algorithm avoids auxiliary containers such as lists or buffers. This direct approach reduces overhead associated with intermediate data structures and keeps the call stack as the sole source of temporary storage. The recursion depth corresponds to the height of the tree, allowing the method to scale naturally with the tree’s shape without additional bookkeeping.

Overall, the implementation delivers a concise transformation from a binary tree to its string form while handling all structural variations of the input.

Imagine a tree made of numbers where every spot can have branches going down to the left or to the right. This code is like a little explorer setting out to visit every single spot in that tree to write down the numbers it sees.

The explorer starts at the very top of the tree and writes down the number sitting there. Then, the explorer looks to see if there are any branches below. If there is a branch on the left, the explorer climbs down, puts parentheses around everything it finds there to keep it tidy, and adds those to the list. After that, it does the exact same thing for any branch on the right. If a spot is empty, the explorer just keeps moving along to the next one. By the time the journey is finished, all the numbers from the tree are lined up in a single string of text.

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++	Java		Python						TS
	WalkCCC	C++	Java		Python
	leetcode.ca	C++	Java		Python		Rust			Go	TS
	LeetcodeHelp	C++	Java		Python
	Progiez	C++	Java		Python
github	BigEggStudy					C#
	black-shadows	C++
	chandansgowda				Python
	charles-wangkai		Java
	DimitrisJim			JS
	everthis			JS
	fartem							Ruby
	fengvyi	C++
	fpdjsns	C++
	gouthampradhan		Java
	JoshCrozier			JS
	keineahnung2345	C++
	Krazune	C++
	linouk23	C++
	lkwq007				Python
	ruoru						Rust
	suxrobGM					C#
	varunu28		Java
	vthwang		Java
	yuanliu666								Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
DimitrisJim	JavaScript
everthis	JavaScript
fartem	Ruby
fengvyi	C++
fpdjsns	C++
gouthampradhan	Java
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
linouk23	C++
lkwq007	Python
ruoru	Rust
suxrobGM	C#
varunu28	Java
vthwang	Java
yuanliu666	Kotlin
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