Abstract / Summary

Implement an iterator to traverse a binary search tree in in order fashion one element at a time.

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 77% (1+ million submissions).

Typical patterns to solve this problem:

• Binary Search Tree
• Binary Tree
• Design
• Iterator
• 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 defines a binary search tree iterator that yields the node values in ascending order. The iterator builds a complete in-order traversal of the tree at construction time and then serves elements sequentially through the next method while exposing the availability of further elements via hasNext. The design isolates the traversal logic in a private helper method and stores the result in a list that acts as a queue for subsequent calls.

Construction Phase

During object creation the constructor receives the root of a binary search tree. It initializes an empty list named inorder and immediately triggers a depth-first walk of the tree.

def __init__(self, root: Optional[TreeNode]):
    self.inorder = []
    self.walk(root)

The walk method implements a classic recursive in-order traversal. For each non-null node it first recurses on the left child, appends the node’s value to the inorder list, and finally recurses on the right child.

def walk(self, node):
    if node:
        self.walk(node.left)
        self.inorder.append(node.val)
        self.walk(node.right)

Because the traversal is performed once, the iterator captures the entire sorted sequence up front, eliminating the need for further tree navigation during iteration.

Retrieval of the Next Element

The next method returns the smallest remaining value by removing the first element of the stored list.

def next(self) -> int:
    return self.inorder.pop(0)

By using pop(0), the method delivers values in the order they were recorded during the initial traversal. The removal also shrinks the list, ensuring that subsequent calls progress through the sequence without additional indexing.

Availability Check

The hasNext method reports whether any elements remain to be produced. It inspects the length of the inorder list and returns a Boolean result.

def hasNext(self) -> bool:
    return len(self.inorder) > 0

This check guards against attempts to retrieve values when the iterator has been exhausted, allowing client code to query the iterator safely before invoking next.

Edge Cases Handled

When the input tree is empty, the constructor receives a None root. The walk method immediately returns without modifying the inorder list, leaving it empty. Consequently, hasNext evaluates to False and next is never called, preventing errors.

A tree consisting of a single node triggers a single recursive call that appends that node’s value to the list. The iterator then yields exactly one element before hasNext becomes False.

Repeated calls to hasNext after the iterator is exhausted continue to return False because the list remains empty, demonstrating stable behavior under successive queries.

Performance Optimizations

The primary optimization is the eager construction of the full in-order sequence. By performing the traversal once during initialization, the iterator avoids repeated recursive calls or stack management during each next operation. This results in constant-time retrieval of the next element, as the method merely extracts the first list entry.

Storing the traversal in a Python list provides fast indexed access and efficient memory layout. The use of pop(0) removes the front element without requiring additional data structures such as explicit queues, leveraging the list’s built-in capabilities.

Overall, the design trades a one-time linear pass over the tree and the associated memory consumption for rapid, straightforward iteration thereafter.

Imagine a tree made of numbers. Some numbers are on the left and some are on the right. This code acts like a little helper that visits every single number in that tree, but it does so in a very special order from smallest to biggest.

First, the helper starts at the very top of the tree. It looks to the left as far as it can go to find the smallest number. When it finds a number, it writes it down on a list. Then it goes to the next number and writes that one down too, until the whole list is filled up from smallest to largest.

Whenever someone asks for the next number, the helper takes the very first number from the top of the list and gives it away. It keeps doing this until the list is completely empty.

If someone wants to know if there are still more numbers left to see, the helper just checks if the list still has anything inside it. If the list has numbers, it says yes. If the list is empty, it says no.

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++	Python		Java							TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java	JS		Rust			Go	TS
	LeetcodeHelp	C++	Python		Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python		Java
github	aylei							Rust
	begeekmyfriend						C
	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai				Java
	chenyanzhe	C++
	everthis					JS
	fartem								Ruby
	FelixFan1122			C#
	fengvyi	C++
	fpdjsns	C++
	gaosq0604		Python
	Garvit244		Python
	halfrost										Go
	haoel	C++
	JoshCrozier					JS
	keineahnung2345	C++
	Krazune	C++
	lennylxx	C++
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	shreymehul			C#
	suxrobGM			C#
	varunu28				Java
	vli02						C
	vthwang				Java
	wisdompeak	C++
	XiaotaoGuo	C++
	yuanliu666									Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lennylxx	C++
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
shreymehul	C#
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
XiaotaoGuo	C++
yuanliu666	Kotlin
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