Binary Search Tree Iterator


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.
NOTE: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.


In a binary search tree, in-order traversal retrieves data in sorted order. In general we traverse the tree from left to right, thus we’ll get a sequence in ascending order. With this knowledge in mind, we can easily implement an iterator over a BST.

In-order traversal review

  s ← empty stack
  while (not s.isEmpty() or node ≠ null)
    if (node ≠ null)
      node ← node.left
      node ← s.pop()
      node ← node.right

We cannot directly apply above iterative in-order traversal to the solution, because we are required to use O(h) memory. We can easily overcome this by dividing the total process into two stages. In first stage, we put elements into a stack, the number of elements is O(h). In second stage, we retrieve element.

C++ implementation

 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
class BSTIterator {
    stack<TreeNode*> st;

    BSTIterator(TreeNode *root) {
        auto p = root;
        while (root) {
            root = root->left;

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !st.empty();

    /** @return the next smallest number */
    int next() {
        auto n =;
        auto p = n->right;
        while (p) {
            p = p->left;
        return n->val;

 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout <<;

In our constructor of BSTIterator, we continue to push element of left node into the stack until left node is null. After this, there are O(h) elements in the stack. hasNext() just checks if the stack is empty, which is O(1). In next(), we remove an element from the stack and deal with its right subtree until we push the next smallest element into the stack, the push operations don’t matter, the number of elements in stack remains O(h). (Todo: time complexity analysis)





#include <iostream>
#include <cxxabi.h>
#include <typeinfo>
#include <cstdlib>

struct empty {};

template <typename T, size_t N> struct bar{};

int main() {
  int status;
  char* real_name;

  bar<empty, 17> b;
  const std::type_info& ti = typeid(b);
  real_name = abi::__cxa_demangle(, 0, 0, &status);
  std::cout << << " => " << real_name << " " << status << std::endl;
  return 0;

这个例子的输出为:3barI5emptyLm17EE => bar 0