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

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;
}

Select all Open in new window