Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Binary Search Tree Iterator
Bookmark
Flatten Array
Stack (Optimal)
Morris O(1)
Input
Standard
Complete BST
Sparse BST
Custom
tree
=
[7, 3, 15, null, null, 9, 20]
7
3
15
9
20
BSTIterator
stack
output
lazy inorder: stack = path to the next smallest
7
3
15
9
20
BSTIterator
stack
output
lazy inorder: stack = path to the next smallest
7
3
node
15
9
20
constructor
stack
7
3
top
output
stack.push(
3
)
7
3
node
15
9
20
next()
stack
7
top
output
next(): node = stack.pop() =
3
7
node
3
#1
15
9
20
next()
stack
output
3
next(): node = stack.pop() =
7
7
3
#1
15
9
node
20
next()
stack
15
9
top
output
3
stack.push(
9
)
7
#2
3
#1
15
9
node
20
next()
stack
15
top
output
3
7
next(): node = stack.pop() =
9
7
#2
3
#1
15
9
#3
node
20
hasNext()
stack
15
top
output
3
7
9
hasNext() →
true
7
#2
3
#1
15
#4
node
9
#3
20
next()
stack
20
top
output
3
7
9
15
next() →
15
7
#2
3
#1
15
#4
9
#3
20
node
next()
stack
output
3
7
9
15
20 has no right child
7
#2
3
#1
15
#4
9
#3
20
#5
done
stack
output
3
7
9
15
20
output: [3, 7, 9, 15, 20]
algo
master
.
io
Step:
Start: the stack lazily holds the path to the next smallest value
0 / 29
Input
Standard
Complete BST
Sparse BST
Custom
tree
=
[7, 3, 15, null, null, 9, 20]
0 / 29
algo
master
.
io
Step:
Start: the stack lazily holds the path to the next smallest value
