camster123
asked on
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.
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;
}
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).
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
@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
#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
ASKER
@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.
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.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
I would lke to thank @pepr and @d-glitch for having solved this problem.