LeetCode #173 Binary Search Tree Iterator
Problem
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.
Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
Solution
Due to dump elements in ascending order, what we have to do in BST is considering in-order traversal. The recursive approach is not suitable for this case, so we should resolve this problem by iterative approach with a stack which needs O(h) extra space. And this is just what problem limits to us.
Complexity
It’s trivial that hasNext operation only needs O(1) time. For next operation, every node will only be push and pop once, so it’s time complexity will be O(1) by amortized.
And it only need O(h) extra space with in-order traversal iteration approach.
