Given two BST print the elements in sorted form

#include <stdio.h>
#include <stdlib.h>
#include <stack>


struct TreeNode {
int data;
TreeNode *left, *right;
};

typedef TreeNode* Tree;

class InorderTraversal {
  public:

InorderTraversal(TreeNode *t):t_(t), cursor_(t) {}


/**
     * Returns NULL at the end of the traversal
     *
     **/

TreeNode* next() {
while (cursor_) {
s_.push(cursor_);
cursor_ = cursor_->left;
}

if (!s_.empty()) {
TreeNode* ret = s_.top();
s_.pop();
cursor_ = ret->right;
return ret;
}

return NULL;
}

void reset() {
cursor_ = t_;
s_ = std::stack<TreeNode*>();
}

  private:

Tree t_;
TreeNode* cursor_;
std::stack<TreeNode*> s_;

};

Tree insert(Tree t, int el) {

if (t == NULL) {
t = (TreeNode *)calloc(sizeof(TreeNode), 1);
t->data = el;
} else {
if(el <= t->data) {
if(t->left) {
insert(t->left, el);
} else {
t->left = (TreeNode *)calloc(sizeof(TreeNode), 1);
t->left->data = el;
}
} else {
if(t->right) {
insert(t->right, el);
} else {
t->right = (TreeNode *)calloc(sizeof(TreeNode), 1);
t->right->data = el;
}
}
}

return t;
}


int main() {
int i;
Tree t1 = NULL;
Tree t2 = NULL;

for (i = 10; i >= 6; i--) {
t1 = insert(t1, i);
}

for (i = 12; i >= 6; i--) {
t2 = insert(t2, i);
}

InorderTraversal s1(t1);
InorderTraversal s2(t2);

TreeNode *n1 = s1.next(), *n2 = s2.next();

while (n1 && n2) {
if (n1->data < n2->data) {
printf("%d ", n1->data);
n1 = s1.next();
} else {
printf("%d ", n2->data);
n2 = s2.next();
}
}

while (n1) {
printf("%d ", n1->data);
n1 = s1.next();
}

while (n2) {
printf("%d ", n2->data);
n2 = s2.next();
}

printf("\n");
}
Advertisements