I think Morris Traversal meets the requirement of average O(1) time and O(h) space (or even better, O(1) space). Since traversing any tree will at least visit n nodes, if the total time complexity for getting n nodes is O(n), then the average time complexity for iterating each node can be considered as O(1).

The Morris Traversal time complexity for traversing all n nodes is O(n), and the averaged time complexity for getting each node is O(1); the space complexity is O(1) for storing only the current node. Using the Morris Traversal method to perform an inorder traversal on BST will generate the sorted array.

In this case, next() function requires the next smallest element to be returned, so we break the traversing loop every time a node is traversed. Although there is a loop to find the inorder predecessor, which is O(log n) in the worst case, not every node needs this loop and the averaged time complexity is guaranteed to be O(1).

However, the obvious drawback is the Morris Traversal will temporarily change the tree structure. If the tree is used elsewhere before being entirely traversed, this method will cause problems.

public class BSTIterator { private TreeNode root,cur; public BSTIterator(TreeNode root) { root = root; cur = root; } /** @return whether we have a next smallest number */ public boolean hasNext() { return cur != null; } /** @return the next smallest number */ public int next() { int r = 0; while(cur!=null){ if(cur.left==null){ r = cur.val; cur = cur.right; // Got the node, break loop break; }else{ TreeNode node = cur.left; while(node.right!=null&&node.right!=cur){ node = node.right; } if(node.right==null){ node.right = cur; cur = cur.left; }else{ node.right = null; r = cur.val; cur = cur.right; // Got the node, break loop break; } } } return r; } }