• 39.9%

https://leetcode.com/problems/binary-search-tree-iterator/#/description

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

https://discuss.leetcode.com/topic/6575/my-solutions-in-3-languages-with-stack

My solutions in 3 languages with Stack

I use Stack to store directed left children from root.

When next() be called, I just pop one element and process its right child as new root.

The code is pretty straightforward.

So this can satisfy O(h) memory, hasNext() in O(1) time,

But next() is O(h) time.

I can’t find a solution that can satisfy both next() in O(1) time, space in O(h).

Java:

C++:

Python:

https://discuss.leetcode.com/topic/12265/my-solution-in-c-in-average-o-1-time-and-uses-o-h-memory

My Solution in C++, in average O(1) time and uses O(h) memory

https://discuss.leetcode.com/topic/8154/morris-traverse-solution

Morris traverse solution

Traverse a BST from the smallest to the largest, then i solve this question simply use the inorder traversal.
To implement a iterator means we should traverse the tree step by step, so just split the inorder traversal.

https://discuss.leetcode.com/topic/24617/c-using-stack

C++. using stack.

The basic idea behind this solution is that we have to implement inorder iteratively but it will gets split into two functions i.e. hasNext and next.
hasNext() will push all the left elements and check and return accordingly if elements are in the stack.
next() will just pop() the top element from the stack and update the current pointer to right .
For this we are taking a stack and a current pointer.
But maybe I may be wrong in hasNext as the requirement of question is O(1) for hasNext() as well.