Skip to content

1586. Binary Search Tree Iterator II 👍

  • Time: Constructor: $O(h)$, next(), prev(): $O(h)$, hasNext(), hasPrev(): $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
28
29
30
31
32
33
34
35
36
37
38
39
40
class BSTIterator {
 public:
  BSTIterator(TreeNode* root) {
    pushLeftsUntilNull(root);
  }

  bool hasNext() {
    return !nexts.empty();
  }

  int next() {
    auto [root, fromNext] = nexts.top();
    nexts.pop();
    if (fromNext)
      pushLeftsUntilNull(root->right);
    prevsAndCurr.push(root);
    return root->val;
  }

  bool hasPrev() {
    return prevsAndCurr.size() > 1;
  }

  int prev() {
    nexts.push({prevsAndCurr.top(), /*fromNext=*/false});
    prevsAndCurr.pop();
    return prevsAndCurr.top()->val;
  }

 private:
  stack<TreeNode*> prevsAndCurr;
  stack<pair<TreeNode*, /*fromNext=*/bool>> nexts;

  void pushLeftsUntilNull(TreeNode* root) {
    while (root != nullptr) {
      nexts.push({root, /*fromtNext=*/true});
      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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class BSTIterator {
  public BSTIterator(TreeNode root) {
    pushLeftsUntilNull(root);
  }

  public boolean hasNext() {
    return !nexts.isEmpty();
  }

  public int next() {
    Pair<TreeNode, Boolean> pair = nexts.pop();
    TreeNode root = pair.getKey();
    boolean fromNext = pair.getValue();
    if (fromNext)
      pushLeftsUntilNull(root.right);
    prevsAndCurr.push(root);
    return root.val;
  }

  public boolean hasPrev() {
    return prevsAndCurr.size() > 1;
  }

  public int prev() {
    nexts.push(new Pair<>(prevsAndCurr.pop(), /*fromNext=*/false));
    return prevsAndCurr.peek().val;
  }

  private void pushLeftsUntilNull(TreeNode root) {
    while (root != null) {
      nexts.push(new Pair<>(root, /*fromNext=*/true));
      root = root.left;
    }
  }

  private Deque<TreeNode> prevsAndCurr = new ArrayDeque<>();
  private Deque<Pair<TreeNode, /*fromNext=*/Boolean>> nexts = new ArrayDeque<>();
}

 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:
  def __init__(self, root: Optional[TreeNode]):
    self.prevsAndCurr = []
    self.nexts = []
    self._pushLeftsUntilNull(root)

  def hasNext(self) -> bool:
    return len(self.nexts) > 0

  def next(self) -> int:
    root, fromNext = self.nexts.pop()
    if fromNext:
      self._pushLeftsUntilNull(root.right)
    self.prevsAndCurr.append(root)
    return root.val

  def hasPrev(self) -> bool:
    return len(self.prevsAndCurr) > 1

  def prev(self) -> int:
    self.nexts.append((self.prevsAndCurr.pop(), False))
    return self.prevsAndCurr[-1].val

  def _pushLeftsUntilNull(self, root):
    while root:
      self.nexts.append((root, True))
      root = root.left