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

Open in new window

camster123Senior C++ Software EngineerAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

peprCommented:
I did not study details of the algorithm, but why do you think that you have O(1)? You are using the while loop to traverse to the left. You are using rescursion (which is actually a hidden loop and hidden stack -- only using other means). And you are using a stack explicitly. It clearly show at least O(log n).
d-glitchCommented:
Have you tested it on some large, randomly generated binary trees over a wide range of N [2 5 10 25 50 100] to verify its performance?
camster123Senior C++ Software EngineerAuthor Commented:
@pepr, You are correct about 0(Log n). Nonetheless, I just modified the algorithm to be O(1) constant space. Please see below and attached file. Could you comment on this change? Thank you.

#include "stdio.h"
using namespace std;
#include <stack>

 
// BST Node
struct Node
{
    int key;
    struct Node *left;
    struct Node *right;
};

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

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)
                        {
                                      printf("TEMP %d\n",tmp->key);
                                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)
                        {
                                        if (cards.size() > 1)   // This is my latest change for 0(1) space requirement.
                              {
                                              cards.pop();
                              }
                              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;
      }
};

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;
}
Iterator.cpp
Become a CompTIA Certified Healthcare IT Tech

This course will help prep you to earn the CompTIA Healthcare IT Technician certification showing that you have the knowledge and skills needed to succeed in installing, managing, and troubleshooting IT systems in medical and clinical settings.

camster123Senior C++ Software EngineerAuthor Commented:
@d-glitch,
                  May I ask you to look at my comment on 2/21/2016 in response to your answer to my Experts Exchange question?  "Using computational imaging and CMOS imaging sensor chips to filter a specific visible light wavelength"?
                 Today , I will test the algorithm on some large, randomly generated binary trees as you recommended.
                Thank you.
peprCommented:
@camster123: Any recursive algorithm cannot be O(1) concerning the memory space. Any recursive call takes local variables (besides the function call overhead). When solving doubling the number of elements of the processed input, the depth of recursive calls also increases (here also at least O(log n)).

Any tree traversal is always more memory efficient (in practice, not the O()) and faster (getting rid of the function call overhead) than the recursive solution. Anyway, you need to use a stack, and the space complexity will be O(log n). The only disadvantage of the non-recursive solution is that it is slightly more difficult to write it correctly (more error prone).

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
camster123Senior C++ Software EngineerAuthor Commented:
I would lke to thank @pepr and @d-glitch for having solved this problem.
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.