Leetcode

Binary Search Tree Iterator

May 26, 2022 by aAshish

Approach 1: Recursive

  • Time:Constructor: O(n), next(): O(1), hasNext(): O(1)
  • Space:O(n)

C++

 
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)
      return;

    inorder(root->left);
    vals.push_back(root->val);
    inorder(root->right);
  }
};

JAVA

 
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);
  }
}

Python

 
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)

C++

 
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;
    }
  }
};

JAVA

 
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;
    }
  }
}

Python

 
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