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

Solution

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

iterativeInorder(node)
  s ← empty stack
  while (not s.isEmpty() or node ≠ null)
    if (node ≠ null)
      s.push(node)
      node ← node.left
    else
      node ← s.pop()
      visit(node)
      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 {
private:
    stack<TreeNode*> st;

public:
    BSTIterator(TreeNode *root) {
        auto p = root;
        while (root) {
            st.push(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 = st.top();
        st.pop();
        auto p = n->right;
        while (p) {
            st.push(p);
            p = p->left;
        }
        return n->val;
    }
};

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

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)

Advertisements

typeid的输出

使用typeid获取的类型名是经过修饰的,并且如何修饰是实现定义的。要去掉修饰,我们可以使用c++filt__cxx_demangle

我们来看一个例子:

#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(ti.name(), 0, 0, &status);
  std::cout << ti.name() << " => " << real_name << " " << status << std::endl;
  free(real_name);
  return 0;
}

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