# 173. Binary Search Tree Iterator

## Approach 1: Recursive

• Time: Constructor: $O(n)$, next(): $O(1)$, hasNext(): $O(1)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class BSTIterator { public: BSTIterator(TreeNode* root) { inorder(root); } /** @return the next smallest number */ int next() { return vals[i++]; } /** @return whether we have a next smallest number */ bool hasNext() { return i < vals.size(); } private: int i = 0; vector vals; void inorder(TreeNode* root) { if (root == nullptr) return; inorder(root->left); vals.push_back(root->val); inorder(root->right); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class BSTIterator { public BSTIterator(TreeNode root) { inorder(root); } /** @return the next smallest number */ public int next() { return vals.get(i++); } /** @return whether we have a next smallest number */ public boolean hasNext() { return i < vals.size(); } private int i = 0; private List vals = new ArrayList<>(); private void inorder(TreeNode root) { if (root == null) return; inorder(root.left); vals.add(root.val); inorder(root.right); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class BSTIterator: def __init__(self, root: Optional[TreeNode]): self.stack = [] self.pushLeftsUntilNone(root) def next(self) -> int: root = self.stack.pop() self.pushLeftsUntilNone(root.right) return root.val def hasNext(self) -> bool: return self.stack def pushLeftsUntilNone(self, root: Optional[TreeNode]): while root: self.stack.append(root) root = root.left 

## Approach 2: Iterative

• Time: Constructor: $O(h)$, next(): $O(h)$, hasNext(): $O(1)$
• Space: $O(h)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class BSTIterator { public: BSTIterator(TreeNode* root) { pushLeftsUntilNull(root); } int next() { TreeNode* root = stack.top(); stack.pop(); pushLeftsUntilNull(root->right); return root->val; } bool hasNext() { return !stack.empty(); } private: stack stack; void pushLeftsUntilNull(TreeNode* root) { while (root) { stack.push(root); root = root->left; } } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class BSTIterator { public BSTIterator(TreeNode root) { pushLeftsUntilNull(root); } public int next() { TreeNode root = stack.pop(); pushLeftsUntilNull(root.right); return root.val; } public boolean hasNext() { return !stack.isEmpty(); } private Deque stack = new ArrayDeque<>(); private void pushLeftsUntilNull(TreeNode root) { while (root != null) { stack.push(root); root = root.left; } } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class BSTIterator: def __init__(self, root: Optional[TreeNode]): self.stack = [] self._pushLeftsUntilNull(root) def next(self) -> int: root = self.stack.pop() self._pushLeftsUntilNull(root.right) return root.val def hasNext(self) -> bool: return self.stack def _pushLeftsUntilNull(self, root: Optional[TreeNode]) -> None: while root: self.stack.append(root) root = root.left