Binary Search Tree Iterator

Description

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

 

Example:

BSTIterator iterator = new BSTIterator(root);
iterator.next();    // return 3
iterator.next();    // return 7
iterator.hasNext(); // return true
iterator.next();    // return 9
iterator.hasNext(); // return true
iterator.next();    // return 15
iterator.hasNext(); // return true
iterator.next();    // return 20
iterator.hasNext(); // return false

 

Note:

• next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
• You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.

Solution(javascript)

// // 1: Recursion
// const BSTIterator = function (root) {
//   const inOrderTraverse = (node) => {
//     if (node) {
//       inOrderTraverse(node.right)
//       this.list.push(node.val)
//       inOrderTraverse(node.left)
//     }
//   }
//   this.list = []
//   inOrderTraverse(root)
// }
// /**
// * @return 下一个最小的数 * @return {number}
// */
// BSTIterator.prototype.next = function () {
//   return this.list.pop()
// }
// /**
// * @return 是否存在下一个最小的数 * @return {boolean}
// */
// BSTIterator.prototype.hasNext = function () {
//   return this.list.length > 0
// }


// 2: Iterative
const BSTIterator = function (root) {
  this.stack = []
  this.push(root)
}
/**
* @return 下一个最小的数 * @return {number}
*/
BSTIterator.prototype.next = function () {
  const node = this.stack.pop()
  this.push(node.right)
  return node.val
}
/**
* @return 是否存在下一个最小的数 * @return {boolean}
*/
BSTIterator.prototype.hasNext = function () {
  return this.stack.length > 0
}

BSTIterator.prototype.push = function (node) {
  while (node) {
    this.stack.push(node)
    node = node.left
  }
}