Abstract / Summary

Check if a string represents a valid preorder serialization of a binary tree by ensuring correct node and null placement.

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 45% (300k+ submissions).

Typical patterns to solve this problem:

• Binary Tree
• Stack
• 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 determines whether a comma-separated preorder traversal string represents a valid binary tree serialization. It follows a recursive descent approach, consuming tokens from the input sequence while implicitly constructing the tree structure through the call stack. The algorithm succeeds only when the entire token list is consumed exactly once a complete binary tree has been reconstructed.

Key Steps

The function begins by splitting the input string into an array of node tokens.

nodes = preorder.split(",")
pos   = 0

A nested helper, deeper, is defined to process the next token and recursively handle its children. The helper uses the nonlocal declaration to share the mutable index pos with the outer scope.

def deeper():
    nonlocal pos
    if pos == len(nodes):          # not enough nodes
        return False

The first guard checks whether the current position has reached the end of the token list before a node is expected. If this occurs, the function returns False, indicating an incomplete serialization.

The next step reads the current token and advances the index.

    current = nodes[pos]
    pos    += 1

When the token is the special marker "#", it denotes a leaf (null) node. The helper returns True immediately, as no further children need to be processed for a null placeholder.

    if current == "#":    # leaf
        return True

If the token is not a leaf marker, it represents an internal node. The algorithm then recursively validates the left subtree followed by the right subtree. Both recursive calls must succeed for the current subtree to be considered valid.

    return deeper() and deeper()   # process left and right children

After defining the helper, the outer function invokes it once and then verifies that the entire token list has been consumed. The final boolean expression ensures that a valid tree has been built and that no extraneous tokens remain.

return deeper() and pos == len(nodes)   # must be a complete tree and nothing left in the string

Edge Cases Handled

The implementation explicitly checks for the situation where the token stream ends prematurely (pos == len(nodes)). This guards against inputs that lack sufficient nodes to satisfy the expected binary tree structure, such as a single internal node without its required two children.

When the input consists solely of a leaf marker ("#"), the recursion processes the single token, returns True from the leaf branch, and the final position check confirms that no additional tokens exist, correctly identifying the serialization as valid.

If the input contains extra tokens after a complete tree has been formed, the final position comparison (pos == len(nodes)) fails, causing the function to return False. This captures cases where the serialization includes superfluous data beyond a well-formed tree.

The guard for an empty string (which would split into [""]) leads to a mismatch between expected node types and the empty token, ultimately resulting in False because the token is neither "#" nor a valid internal node, and the recursion cannot satisfy the required child calls.

Performance Optimizations

The algorithm processes each token exactly once, advancing the shared index pos in a linear fashion. By using a single mutable index rather than creating new slices or sub-lists for each recursive call, it avoids the overhead of copying data structures.

The recursion leverages short-circuit evaluation (and) when processing left and right children. If the left subtree validation fails, the right subtree is never invoked, preventing unnecessary work on an already invalid branch.

Because the helper function is defined inside the main method, it captures the surrounding variables without additional parameter passing, reducing the call-frame size and improving cache locality for the index variable.

Overall, the design achieves a streamlined traversal that minimizes memory allocations and redundant processing while faithfully adhering to the preorder serialization rules.

Imagine a tree standing in a magic forest where every branch must either have two smaller branches growing from it or end in a tiny leaf. The code reads a list of objects describing this tree one by one. It acts like a helper who travels from the trunk out to every single tip of the branches.

When the helper looks at a piece of the tree, it first checks if there is still one left to look at. If the piece is a special marker that looks like a hashtag, that means it is just a leaf that stops the growth on that path. If it is not a leaf, the helper knows it must continue working by visiting two new spots to see what is growing there. This happens over and over until the helper has visited every single part of the tree. Once all the parts are checked, the code confirms if every piece was used to build a perfect, finished tree without any bits left over on the ground.

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			Go		TS
	LeetcodeHelp	C++	Python		Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fartem						Ruby
	fengvyi	C++
	halfrost							Go
	haoel	C++
	JoshCrozier			JS
	linouk23	C++
	lkwq007		Python
	ruoru					Rust
	suxrobGM								C#
	trung-hn		Python
	varunu28				Java
	wisdompeak	C++
	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
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fengvyi	C++
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
linouk23	C++
lkwq007	Python
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++
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