We help IT Professionals succeed at work.
Get Started

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

camster123
camster123 asked
on
269 Views
Last Modified: 2016-05-09
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

Comment
Watch Question
CERTIFIED EXPERT
Commented:
This problem has been solved!
Unlock 2 Answers and 6 Comments.
See Answers
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

When asked, what has been your best career decision?

Deciding to stick with EE.

Mohamed Asif
Technical Department Head

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

Carl Webster
CTP, Sr Infrastructure Consultant

An Experts Exchange subscription includes unlimited access to online courses.

Get Started
Ask ANY Question

Connect with Certified Experts to gain insight and support on specific technology challenges including:

  • Troubleshooting
  • Research
  • Professional Opinions
Did You Know?

We've partnered with two important charities to provide clean water and computer science education to those who need it most. READ MORE