Abstract / Summary

Given a list of numbers that represents the preorder traversal of a BST create the binary search tree from it.

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 84% (600k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search Tree
• Binary Tree
• Monotonic Stack
• 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 constructs a binary search tree (BST) from a preorder traversal list. It uses a recursive helper named deeper that respects a dynamic upper bound (stop) to decide when a subtree should terminate. The algorithm walks through the preorder array exactly once, advancing a shared index (pos) as nodes are created, and builds the tree in a top-down fashion without auxiliary data structures.

Core Logic

The entry point creates a mutable cursor pos initialized to zero. This cursor tracks the next element of the preorder list that has not yet been placed in the tree.

pos = 0

A nested function deeper(stop) is defined. The parameter stop represents the smallest value that would be illegal for the current subtree; any value larger than stop signals that the subtree must end and control returns to the caller.

def deeper(stop):
    nonlocal pos
    if pos == len(preorder):
        return None
    value = preorder[pos]
    if value > stop:
        return None
    node = TreeNode(value)
    pos += 1
    node.left  = deeper(value)
    node.right = deeper(stop)
    return node

The recursion follows three distinct phases:

1. Termination Check - If the cursor has reached the end of the input, the function returns None, indicating that no further nodes exist.

2. Bound Check - The current preorder value is compared against stop. When the value exceeds the bound, the function returns None, effectively cutting off the current branch.

3. Node Creation and Subtree Construction - A new TreeNode is instantiated with the current value, the cursor is advanced, and the function recursively builds the left subtree with a tighter bound (value) and the right subtree with the original bound (stop). The left recursion ensures that all left descendants are smaller than the node, while the right recursion respects the original upper limit.

The outermost call supplies positive infinity as the initial bound, allowing any integer from the preorder list to become the root.

return deeper(+inf)

Edge Cases Handled

When the preorder list is empty, the initial bound check inside deeper immediately encounters pos == len(preorder) and returns None, resulting in an empty tree.

If the preorder list contains a single element, the first call creates a node, advances pos to the end, and both recursive calls for left and right subtrees encounter the end-of-list condition, yielding None children.

The bound comparison (value > stop) gracefully handles cases where the preorder sequence contains values that belong to higher levels of the tree. For example, when constructing the right subtree of a node, the function will stop recursing leftward as soon as it sees a value that exceeds the parent’s bound, thereby correctly switching to the right side without extra state.

Performance Optimizations

The algorithm achieves linear traversal by maintaining a single mutable index (pos) that never backtracks. Each element of the preorder list is examined exactly once, and the recursion depth mirrors the height of the resulting BST, avoiding the need for explicit stacks or auxiliary containers.

By passing the upper bound (stop) down the recursion chain, the implementation eliminates the need for range checks that would otherwise require scanning previously built nodes. This bound propagation ensures that the decision to create or skip a node is made in constant time per call.

Using nonlocal for pos avoids copying the cursor into each recursive frame, reducing overhead associated with argument passing. The direct construction of TreeNode objects without intermediate lists or temporary structures further minimizes memory churn.

Overall, the design leverages the inherent order of preorder traversal to reconstruct the BST efficiently, with minimal auxiliary state and a tight recursion pattern that aligns with the natural shape of the tree.

Imagine building a tall tower out of blocks using a special list of numbers that tells you exactly which order to place them. Each new block needs to know where to go based on the number it has.

The computer keeps track of which number it is looking at next in the list. There is a helper function that acts like a little explorer. The explorer carries a rule called stop, which says that if a number is too big, it cannot belong in the current part of the tower.

When the explorer starts, it looks at the first number in the list. It creates a new piece of the tower with that value. Then, the explorer tries to build the left side of that piece. To make the left side, it uses the current number as the new limit for how big those blocks can be. After finishing the left side, it goes back and tries to build the right side using the original limit that it started with. This keeps happening over and over until every number from the list is used to create a new part of the tower. Because the explorer keeps passing these limits along, the blocks always end up in the right spots to form a perfect shape.

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++	Java	Python								TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python						Go	Rust	TS
	LeetcodeHelp	C++	Java	Python
	MemoryLimitExceeded	C++		Python
	Progiez	C++	Java	Python
github	AdelDaniel								Dart
	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai		Java
	DimitrisJim						C
	everthis				JS
	fartem							Ruby
	fpdjsns	C++
	fsq	C++
	Garvit244			Python
	JoshCrozier				JS
	keineahnung2345	C++
	Krazune		Java
	lkwq007			Python
	lzl124631x	C++
	sonugiri1043	C++
	suxrobGM					C#
	varunu28		Java
	vli02						C
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
AdelDaniel	Dart
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fpdjsns	C++
fsq	C++
Garvit244	Python
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	Java
lkwq007	Python
lzl124631x	C++
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	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