Skip to content

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<int> 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<Integer> 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<TreeNode*> 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<TreeNode> 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