# Binary Search Tree Iterator
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/binary-search-tree-iterator)
Canonical: https://scaleengineer.com/dsa/problems/binary-search-tree-iterator
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design), [Iterator](https://scaleengineer.com/dsa/patterns/iterator)
**Data structures:** Stack, Tree, Binary Tree, Binary Search Tree
**Companies:** [LinkedIn](https://scaleengineer.com/companies/linkedin), [Media.net](https://scaleengineer.com/companies/media.net)
---
## Problem
Implement the `BSTIterator` class that represents an iterator over the **[in-order traversal](https://en.wikipedia.org/wiki/Tree%5Ftraversal#In-order%5F%28LNR%29)** of a binary search tree (BST):

* `BSTIterator(TreeNode root)` Initializes an object of the `BSTIterator` class. The `root` of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
* `boolean hasNext()` Returns `true` if there exists a number in the traversal to the right of the pointer, otherwise returns `false`.
* `int next()` Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to `next()` will return the smallest element in the BST.

You may assume that `next()` calls will always be valid. That is, there will be at least a next number in the in-order traversal when `next()` is called.

**Example 1:**

![](https://assets.glich.co/dsa/binary-search-tree-iterator/image0.png) 

**Input**
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
**Output**
[null, 3, 7, true, 9, true, 15, true, 20, false]

**Explanation**
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // return 3
bSTIterator.next();    // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 20
bSTIterator.hasNext(); // return False

**Constraints:**

* The number of nodes in the tree is in the range `[1, 105]`.
* `0 <= Node.val <= 106`
* At most `105` calls will be made to `hasNext`, and `next`.

**Follow up:**

* Could you implement `next()` and `hasNext()` to run in average `O(1)` time and use `O(h)` memory, where `h` is the height of the tree?

# Approaches
## Flattening the BST
This approach involves performing a full in-order traversal of the BST during the initialization of the iterator. All the node values are stored in a dynamic array or list in their sorted, in-order sequence. The iterator then simply traverses this pre-computed list.
**Time:** Constructor: O(N), `next()`: O(1), `hasNext()`: O(1), where N is the number of nodes in the tree. · **Space:** O(N), to store the values of all N nodes in the list.
**Pros:** Simple to understand and implement.; The `next()` and `hasNext()` operations are very fast (true O(1)) after the initial setup.
**Cons:** High space complexity of O(N), which can be significant for large trees.; The constructor performs O(N) work upfront, which is inefficient if the iterator is only used to get a few elements.
### Explanation
The core idea is to convert the tree traversal problem into a simple list iteration problem.

**Constructor `BSTIterator(TreeNode root)`:**
1. Initialize an empty list, for example, an `ArrayList<Integer>`.
2. Implement a helper function, typically recursive, to perform an in-order traversal (Left -> Root -> Right).
3. Call this helper function starting from the `root` to populate the list with all node values.
4. Initialize an index or pointer to the beginning of the list (e.g., `index = 0`).

**`hasNext()` method:**
1. This method simply checks if the current index is within the bounds of the list (i.e., `index < list.size()`).

**`next()` method:**
1. It retrieves the element at the current index from the list.
2. Increments the index to point to the next element.
3. Returns the retrieved value.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class BSTIterator {
    private List<Integer> nodes;
    private int index;

    public BSTIterator(TreeNode root) {
        this.nodes = new ArrayList<>();
        this.index = 0;
        this._inorder(root);
    }

    private void _inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        _inorder(root.left);
        this.nodes.add(root.val);
        _inorder(root.right);
    }

    public int next() {
        return this.nodes.get(this.index++);
    }

    public boolean hasNext() {
        return this.index < this.nodes.size();
    }
}
```
### Algorithm
- In the constructor, create an empty list `nodes`.
- Perform a recursive in-order traversal of the tree.
- During the traversal, add each node's value to the `nodes` list.
- Initialize an `index` to 0.
- For `next()`, return `nodes.get(index)` and then increment `index`.
- For `hasNext()`, return `true` if `index` is less than the size of `nodes`, `false` otherwise.

## Controlled In-order Traversal (Lazy Approach)
This approach simulates the in-order traversal iteratively using a stack, processing nodes only when they are requested. This avoids the need to store all nodes at once, leading to much better space complexity. It's often called a 'lazy' approach because it does just enough work for each `next()` call.
**Time:** `hasNext()`: O(1). `next()`: Amortized O(1). While a single call can take up to O(h) in the worst case, each node is pushed and popped exactly once over the entire traversal, making the average time O(1). · **Space:** O(h), where h is the height of the tree. The stack stores at most h nodes, which corresponds to the longest path from the root to a leaf.
**Pros:** Optimal space complexity of O(h), satisfying the follow-up question.; Lazy evaluation: work is distributed across `next()` calls, which is efficient if the full tree is not traversed.; Average O(1) time complexity for `next()` and `hasNext()`.
**Cons:** The implementation is more complex than the flattening approach.; The time complexity for a single `next()` call is not strictly O(1) and can be O(h) in some cases.
### Explanation
Instead of pre-computing the entire traversal, we use a stack to keep track of the path to the next smallest node. This is analogous to how a recursive in-order traversal uses the call stack.

**Constructor `BSTIterator(TreeNode root)`:**
1. Initialize an empty `Stack<TreeNode>`.
2. To prepare for the first `next()` call (which should return the smallest element), we must find the leftmost node. We do this by pushing the `root` and all its subsequent left children onto the stack.

**`hasNext()` method:**
1. The iterator has a next element if and only if the stack is not empty.

**`next()` method:**
1. The node at the top of the stack is the next smallest element. Pop this node from the stack.
2. Let the popped node be `currentNode`.
3. After processing `currentNode`, the next element in the in-order sequence is the smallest element in `currentNode`'s right subtree. 
4. If `currentNode` has a right child, push that right child and all of its left descendants onto the stack. This sets up the stack for the subsequent `next()` call.
5. Return the value of `currentNode`.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class BSTIterator {
    private Stack<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        this.stack = new Stack<>();
        // Push all the left nodes of the root onto the stack
        this._leftmostInorder(root);
    }

    private void _leftmostInorder(TreeNode root) {
        while (root != null) {
            this.stack.push(root);
            root = root.left;
        }
    }

    /** @return the next smallest number */
    public int next() {
        // The top of the stack is the next smallest node
        TreeNode topmostNode = this.stack.pop();

        // If the popped node has a right child, we need to
        // find the smallest node in its right subtree.
        if (topmostNode.right != null) {
            this._leftmostInorder(topmostNode.right);
        }

        return topmostNode.val;
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !this.stack.isEmpty();
    }
}
```
### Algorithm
- Initialize a stack in the constructor.
- Create a helper function `_leftmostInorder(node)` that pushes a node and all its left children onto the stack.
- Call `_leftmostInorder(root)` in the constructor to initialize the stack with the path to the smallest element.
- For `hasNext()`, check if the stack is empty.
- For `next()`:
  - Pop a node from the stack. This is the current smallest node.
  - If the popped node has a right child, call `_leftmostInorder` on its right child to prepare for the next call.
  - Return the value of the popped node.

# Solutions
### Java

```java
import java.util.ArrayList ; import java.util.Collections ; import java.util.List ; import java.util.Stack ; public class Binary_Search_Tree_Iterator { /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class BSTIterator { Stack < TreeNode > sk ; // @note:@memorize: important feature, min is always going left branch to leaf public BSTIterator ( TreeNode root ) { sk = new Stack <>(); // all the way to leftmost leaf while ( root != null ) { sk . push ( root ); root = root . left ; } } /** @return whether we have a next smallest number */ public boolean hasNext () { return ! sk . isEmpty (); } /** @return the next smallest number */ public int next () { TreeNode minNode = sk . pop (); TreeNode current = minNode ; // update stack, possible next time min is frmo its right-then-left branch if ( current . right != null ) { current = current . right ; // same logic as in constructor while ( current != null ) { sk . push ( current . left ); current = current . left ; } } return minNode . val ; } } /** * Your BSTIterator will be called like this: * BSTIterator i = new BSTIterator(root); * while (i.hasNext()) v[f()] = i.next(); */ } ############ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class BSTIterator { private Deque < TreeNode > stack = new LinkedList <>(); public BSTIterator ( TreeNode root ) { for (; root != null ; root = root . left ) { stack . offerLast ( root ); } } public int next () { TreeNode cur = stack . pollLast (); for ( TreeNode node = cur . right ; node != null ; node = node . left ) { stack . offerLast ( node ); } return cur . val ; } public boolean hasNext () { return ! stack . isEmpty (); } } /** * Your BSTIterator object will be instantiated and called as such: * BSTIterator obj = new BSTIterator(root); * int param_1 = obj.next(); * boolean param_2 = obj.hasNext(); */
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root */ var BSTIterator =
  function (root) {
    this.stack = [];
    for (; root != null; root = root.left) {
      this.stack.push(root);
    }
  };
/** * @return {number} */ BSTIterator.prototype.next = function () {
  let cur = this.stack.pop();
  let node = cur.right;
  for (; node != null; node = node.left) {
    this.stack.push(node);
  }
  return cur.val;
};
/** * @return {boolean} */ BSTIterator.prototype.hasNext = function () {
  return this.stack.length > 0;
}; /** * Your BSTIterator object will be instantiated and called as such: * var obj = new BSTIterator(root) * var param_1 = obj.next() * var param_2 = obj.hasNext() */

```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class BSTIterator : def __init__ ( self , root : TreeNode ): self . stack = [] self . _leftmost_inorder ( root ) def _leftmost_inorder ( self , node ): while node : self . stack . append ( node ) node = node . left def next ( self ) -> int : cur = self . stack . pop () node = cur . right self . _leftmost_inorder ( node ) return cur . val def hasNext ( self ) -> bool : return len ( self . stack ) > 0 # Your BSTIterator object will be instantiated and called as such: # obj = BSTIterator(root) # param_1 = obj.next() # param_2 = obj.hasNext() ############# # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class BSTIterator : def __init__ ( self , root : TreeNode ): self . stack = [] while root : self . stack . append ( root ) root = root . left def next ( self ) -> int : cur = self . stack . pop () node = cur . right while node : # deplicated while block self . stack . append ( node ) node = node . left return cur . val def hasNext ( self ) -> bool : return len ( self . stack ) > 0 # Your BSTIterator object will be instantiated and called as such: # obj = BSTIterator(root) # param_1 = obj.next() # param_2 = obj.hasNext()
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/binary-search-tree-iterator/ // Time: O(1) amortized // Space: O(H) class BSTIterator { private: stack < TreeNode *> s ; void pushNodes ( TreeNode * node ) { while ( node ) { s . push ( node ); node = node -> left ; } } public: BSTIterator ( TreeNode * root ) { pushNodes ( root ); } int next () { auto node = s . top (); s . pop (); pushNodes ( node -> right ); return node -> val ; } bool hasNext () { return s . size (); } };
```