Abstract / Summary

Given a sorted list of numbers create a balanced 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 76% (2+ million submissions).

Typical patterns to solve this problem:

• Array
• Binary Search Tree
• Binary Tree
• Divide And Conquer
• 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 sorted integer array into a height-balanced binary search tree (BST). The conversion is performed by a recursive helper method that selects the middle element of a sub-range as the root, then recursively builds left and right sub-trees from the left and right halves of the range. The public entry point simply invokes this helper with the full range of the input list.

Recursive Construction

The heart of the algorithm lies in the add method. It receives the original list together with two integer indices that delimit the current sub-range. The method first checks for termination conditions: an empty list or a range where the start index is not less than the end index. In those cases it returns None, which signals that a leaf node has been reached.

def add(self, nums, begin, end):
    if not nums or begin >= end:
        return None

When the range is valid, the midpoint is computed using integer division. This midpoint determines the value that becomes the root of the current subtree. By using integer division, the algorithm consistently picks the lower middle element for even-length ranges, which preserves the balanced property.

    mid = (begin + end) // 2

The left subtree is constructed by recursively calling add on the segment that lies before the midpoint, while the right subtree is built from the segment that follows the midpoint. The recursion naturally terminates when the sub-range collapses, producing None for missing children.

    left  = self.add(nums, begin, mid)
    right = self.add(nums, mid + 1, end)

Finally, a new TreeNode instance is created with the midpoint value and the previously built left and right children. This node is returned up the call stack, gradually assembling the full BST.

    return TreeNode(nums[mid], left, right)

Public Interface

The sortedArrayToBST method serves as the entry point for callers. It forwards the original list along with the start index 0 and the exclusive end index len(nums) to the recursive helper. By using an exclusive end index, the method avoids off-by-one errors and aligns with Python’s slicing conventions, even though slicing is not performed directly.

def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
    return self.add(nums, 0, len(nums))

Edge Cases Handled

The code explicitly checks for an empty input list. When nums is empty, the guard if not nums triggers, causing the helper to return None. This ensures that the public method returns None for an empty array, representing an empty tree.

Another edge condition is when the begin index meets or exceeds the end index. This situation occurs when a sub-range has been reduced to zero elements, which is the natural base case for recursion. By returning None in this scenario, the algorithm correctly terminates the branch without attempting to access out-of-range elements.

The midpoint calculation using integer division gracefully handles both odd and even sized sub-ranges. For an even number of elements, the lower middle index is chosen, which still yields a balanced tree because the sizes of the left and right sub-ranges differ by at most one element.

Performance Optimizations

The implementation avoids creating new list slices for each recursive call. Instead of passing sub-lists, it passes index boundaries that reference the original list. This approach eliminates the overhead of copying data and reduces memory pressure, especially for large input arrays.

By selecting the middle element as the root at each step, the algorithm guarantees that the depth of the tree grows logarithmically relative to the number of elements. This balanced construction prevents the formation of degenerate (linear) trees, which would degrade operations that rely on tree height.

The recursion depth is bounded by the height of the resulting tree. Because the tree is balanced, the recursion stack remains shallow, which minimizes the risk of stack overflow for typical input sizes.

The use of a single TreeNode constructor call per node ensures that node creation is performed exactly once per element, avoiding redundant allocations. The left and right child references are assigned directly from the results of the recursive calls, which streamlines the assembly of the tree structure.

Imagine a big pile of numbers organized in a perfect line from smallest to largest. To turn this line into a special tree shape, pick the number right in the middle to be the crown at the top. Everything to the left of that middle spot becomes the left branch, and everything to the right becomes the right branch. Now, just repeat that same trick for each new branch. You keep picking the middle of the smaller lines until every single number has its own place in the tree. It is like building a tower by always finding the center point to keep everything balanced and tidy.

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		Rust	C#	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
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	DimitrisJim				C
	everthis							JS
	fartem								Ruby
	FelixFan1122						C#
	fengvyi	C++
	fpdjsns	C++
	gaosq0604		Python
	Garvit244		Python
	halfrost										Go
	haoel	C++
	JoshCrozier							JS
	lennylxx				C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	qiyuangong		Python
	ruoru					Rust
	shreymehul						C#
	sonugiri1043	C++
	suxrobGM			Java
	varunu28			Java
	vli02				C
	vthwang			Java
	XiaotaoGuo	C++
	yuanliu666									Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, 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
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	Java
varunu28	Java
vli02	C
vthwang	Java
XiaotaoGuo	C++
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