We help IT Professionals succeed at work.

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

on
269 Views
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;
}
``````
Comment
Watch Question
CERTIFIED EXPERT
Commented:
This problem has been solved!
###### Why Experts Exchange?

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.

Jim Murphy
Programmer at Smart IT Solutions

Deciding to stick with EE.

Mohamed Asif

Being involved with EE helped me to grow personally and professionally.

Carl Webster
CTP, Sr Infrastructure Consultant