Abstract / Summary

Given an array of integers, create a binary tree where each node is the largest value in its subarray, making it the root of that subtree.

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 86% (400k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Tree
• Divide And Conquer
• 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 builds a maximum binary tree from a list of distinct integers. The algorithm follows the definition of a maximum binary tree: the root is the maximum element of the array, the left subtree is recursively built from the sub-array left of the maximum, and the right subtree from the sub-array right of the maximum. The function returns the root node of the constructed tree or None when the input list is empty.

Key Steps

The method begins with a guard clause that immediately returns None for an empty input, ensuring that recursive calls on empty slices terminate correctly.

if not nums:
    return None

Next, the algorithm scans the entire list to locate the greatest value and its index. Two variables, high and pos, keep track of the current maximum and its position. The loop iterates over the range of indices, updating these variables whenever a larger element is encountered.

high = nums[0]
pos  = 0
for i in range(len(nums)):
    if high < nums[i]:
        high = nums[i]
        pos = i

After identifying the maximum element, the function creates a new tree node. The left child is produced by a recursive call on the slice preceding the maximum, and the right child by a recursive call on the slice following the maximum. The TreeNode constructor receives the value and the two subtrees.

return TreeNode(
    high,
    self.constructMaximumBinaryTree(nums[:pos]),
    self.constructMaximumBinaryTree(nums[pos+1:])
)

Edge Cases Handled

The implementation explicitly handles the situation where the input list is empty. By checking if not nums at the start, the function avoids attempting to access nums[0] on an empty sequence, which would raise an exception. This guard also serves as the base case for the recursion: when a recursive call receives an empty slice, it returns None, correctly representing a missing child in the binary tree.

Another implicit edge case is the scenario where the maximum element resides at the first or last position of the list. In those cases, one of the slices (nums[:pos] or nums[pos+1:]) becomes empty. The guard clause ensures that the subsequent recursive call on the empty slice yields None, resulting in a leaf node with only one child, which matches the definition of the maximum binary tree.

Performance Optimizations

The code performs a single linear scan to locate the maximum element for each recursive invocation. By maintaining high and pos during the scan, it avoids the overhead of calling built-in functions such as max and index separately. This reduces the number of passes over the data and eliminates the creation of intermediate objects that those functions might generate.

The recursion directly works with Python list slicing (nums[:pos] and nums[pos+1:]). While slicing creates new list objects, the algorithm confines each slice to the exact sub-range needed for the next recursive step, preventing unnecessary copying of unrelated elements. This localized slicing contributes to a memory pattern that aligns with the recursive depth of the tree, allowing Python’s garbage collector to reclaim the temporary slices promptly after each call returns.

Imagine you have a big pile of numbered blocks. To build this special tower, you first hunt through all the blocks to find the one with the biggest number on it. Once you find that champion, you put it at the very top of your creation. Now you have a left side and a right side left over from your pile. You repeat the process for all the blocks left on the left side, and you repeat it again for all the blocks on the right side. You keep doing this over and over again, finding the biggest piece for each part of the structure, until every single block has a place in the tower. It is like sorting everything by choosing the biggest king of the castle for every little room until the whole house is finished.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
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		Rust			C	Go	TS
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai		Java
	DimitrisJim								C
	fartem						Ruby
	fengvyi	C++
	fsq	C++
	gouthampradhan		Java
	JoshCrozier							JS
	keineahnung2345	C++
	Krazune	C++
	lkwq007			Python
	lzl124631x	C++
	MacJim	C++
	qiyuangong		Java
	ruoru					Rust
	sonugiri1043	C++
	suxrobGM				C#
	varunu28		Java
	wisdompeak	C++
	YuriSpiridonov			Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
fartem	Ruby
fengvyi	C++
fsq	C++
gouthampradhan	Java
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lkwq007	Python
lzl124631x	C++
MacJim	C++
qiyuangong	Java
ruoru	Rust
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
wisdompeak	C++
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