#include "stdio.h"
using namespace std;
#include <stack>
// BST Node
struct Node
{
int key;
struct Node *left;
struct Node *right;
};
class Iterator
{
private:
Node* thisRoot;
Node* thisCurr;
Node* thisMaximum;
stack<Node*> cards;
void InOrder(Node* root, Node*& succ, int key)
{
// Base case
if (root == NULL) return ;
// If key is present at root
if (root->key == key)
{
// the minimum value in right subtree is successor
if (root->right != NULL)
{
Node* tmp = root->right ;
while (tmp->left)
{
cards.push(tmp);
tmp = tmp->left;
}
succ = tmp ;
}
return ;
}
// If key is smaller than root's key, go to left subtree
if (root->key > key)
{
succ = root;
InOrder(root->left, succ, key) ;
}
else
{
if (key == thisMaximum->key)
{
return;
}
if (cards.size() > 0)
{
succ = cards.top();
if (succ != NULL && key < thisMaximum->key)
{
InOrder(
root->right,
succ,
key) ;
}
}
}
}
Node* HelperGoLeft(Node* where)
{
if (where == NULL)
{
return NULL;
}
if (where->left == NULL & where->right == NULL)
{
return where;
}
return HelperGoLeft(where->left);
}
Node* HelperGoRight(Node* where)
{
if (where == NULL)
{
return NULL;
}
if (where->left == NULL & where->right == NULL)
{
return where;
}
return HelperGoRight(where->right);
}
public:
Iterator(Node* theTree)
{
thisRoot = theTree;
thisCurr = HelperGoLeft(thisRoot);
thisMaximum = HelperGoRight(thisRoot);
}
int next()
{
struct Node* successor(NULL);
InOrder(thisRoot, thisCurr, thisCurr->key);
return thisCurr->key;
}
bool HasNext()
{
return thisRoot != NULL && thisCurr->key < thisMaximum->key;
}
};
This is my C++ test driver program.
// A utility function to create a new BST node
Node *newNode(int item)
{
Node *temp = new Node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
/* A utility function to insert a new node with given key in BST */
Node* insert(Node* node, int key)
{
if (node == NULL) return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
return node;
}
int main(int argc, char* argv[])
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
Node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
insert(root, 100);
insert(root, 90);
insert(root, 110);
Iterator* test = new Iterator(root);
while( test->HasNext())
{
printf("%d\n", test->next());
}
return 1;
}
Experts Exchange always has the answer, or at the least points me in the correct direction! It is like having another employee that is extremely experienced.
When asked, what has been your best career decision?
Deciding to stick with EE.
Being involved with EE helped me to grow personally and professionally.
Connect with Certified Experts to gain insight and support on specific technology challenges including:
We've partnered with two important charities to provide clean water and computer science education to those who need it most. READ MORE