LeetCode Q173: 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.

	/**
	* Definition for binary tree
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class BSTIterator {
	public:
	BSTIterator(TreeNode *root) {
	if(root==NULL)
	return;
	inorderTraverse(root, sorted);
	idx=0;
	}
	/** @return whether we have a next smallest number */
	bool hasNext() {
	if(sorted.empty())
	return false;
	return idx<=sorted.size()-1;
	}
	/** @return the next smallest number */
	int next() {
	int res=sorted[idx]->val;
	idx++;
	return res;
	}
	void inorderTraverse(TreeNode* root, vector<TreeNode*>& sorted){
	if(root==NULL)
	return;
	inorderTraverse(root->left, sorted);
	sorted.push_back(root);
	inorderTraverse(root->right, sorted);
	}
	vector<TreeNode*> sorted;
	int idx;
	};
	/**
	* Your BSTIterator will be called like this:
	* BSTIterator i = BSTIterator(root);
	* while (i.hasNext()) cout << i.next();
	*/

view raw Q173BinarySearchTreeIterator.cpp hosted with ❤ by GitHub

Round 2 solution:

	/**
	* Definition for binary tree
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class BSTIterator {
	public:
	BSTIterator(TreeNode *root) {
	if(root!=NULL){
	myStack.push(root);
	curNode=root->left;
	}else{
	curNode=NULL;
	}
	}
	/** @return whether we have a next smallest number */
	bool hasNext() {
	return !(curNode==NULL&&myStack.empty());
	}
	/** @return the next smallest number */
	int next() {
	int res = 0;
	while(true){
	if(curNode==NULL&&!myStack.empty()){
	TreeNode* top = myStack.top();
	res = top->val;
	myStack.pop();
	curNode=top->right;
	return res;
	}else{
	while(curNode!=NULL){
	myStack.push(curNode);
	curNode=curNode->left;
	}
	}
	}
	}
	stack<TreeNode*> myStack;
	TreeNode* curNode;
	};
	/**
	* Your BSTIterator will be called like this:
	* BSTIterator i = BSTIterator(root);
	* while (i.hasNext()) cout << i.next();
	*/

view raw Q173Rnd2.cpp hosted with ❤ by GitHub