Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
Failed to load latest commit information.

< Previous                  Next >

173. Binary Search Tree Iterator (Medium)

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.



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



  • 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.

Related Topics

[Stack] [Tree] [Design]

Similar Questions

  1. Binary Tree Inorder Traversal (Medium)
  2. Flatten 2D Vector (Medium)
  3. Zigzag Iterator (Medium)
  4. Peeking Iterator (Medium)
  5. Inorder Successor in BST (Medium)
You can’t perform that action at this time.