troubleshooting Question

# Is this a possibly new algorithm using C++ to provide an inorder iterator for Binary Search Trees?

C++Algorithms
This morning I developed a possibly new algorithm using C++ to provide an inorder iterator for Binary Search Trees. Please tell me if it is correct and whether it is a new algorithm. This is not a Homework question. I was given this problem as a test of my Coderrank algorithm skills yesterday.

I just realized last night that I can reduce the memory and space requirements of my algorithm to constant big 0(1) instead of big 0(log N) by popping the STL stack after it is queried.

``````#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;
}
``````
pepr
###### Learn from the best

Network and collaborate with thousands of CTOs, CISOs, and IT Pros rooting for you and your success.

Andrew Hancock - VMware vExpert
See if this solution works for you by signing up for a 7 day free trial.