I got this problem statement in one of my technical interviews. I didn't find solution to this problem on google. SO I attempted it myself . It was fun solving this problem and I enjoyed it. Here is solution.
#include#include #include typedef struct node { struct node* left; struct node* right; struct node* parent; int data; }T; T* head=NULL; void add_node(int data) { T* t = (T *)malloc(sizeof(T)); t->left=NULL;t->right=NULL;t->parent=NULL;t->data=data; if (head==NULL) { head = t; } else { T* tmp = head; while (1) { if (data < tmp->data) { // should go on left side if (tmp->left==NULL) { t->parent=tmp; tmp->left = t; break; } tmp=tmp->left; } else { // should go on right side if (tmp->right==NULL) { t->parent = tmp; tmp->right = t; break; } tmp=tmp->right; } } } } void myt(T* root) { if (root==NULL) { return; } int left_back=0,right_back=0; while(1) { if (root->left==NULL && root->right==NULL) { // I am child node . print my data and move to my parent printf(" %d",root->data); if (root->parent==NULL) { // we are THE ROOT . done traverse return; } if (root==(root->parent)->left) { // I was left child of parent left_back=1; right_back=0; } else { // I was right child of parent right_back=1; left_back=0; } root=root->parent; continue; } if (left_back==1) { // we have come back from left child . print data printf(" %d",root->data); if (root->right!=NULL) { root=root->right; left_back=0;right_back=0; continue; } else { // we dont have right child . we have to back track if (root->parent==NULL) { // we are THE ROOT. Done traverse return; } if(root==(root->parent)->left) { left_back=1;right_back=0; } else { left_back=0;right_back=1; } root=root->parent; continue; } } if (right_back==1) { // we have come back from right node. we have to back track if (root->parent==NULL) { // we are THE ROOT. Done traverse return; } if(root==(root->parent)->left) { left_back=1;right_back=0; } else { left_back=0;right_back=1; } root=root->parent; continue; } if(root->left!=NULL) { left_back=0;right_back=0; root=root->left; continue; } else { // left child is not present. print data and move to right printf(" %d",root->data); root=root->right; left_back=0;right_back=0; } } } void traverse(T* h) { if (h==NULL) {return;} traverse(h->left); printf(" %d",h->data); traverse(h->right); } void main() { clrscr(); printf("\n enter elements \n"); int n; while(1) { scanf("%d",&n); if(n==0) { break; } add_node(n); } printf("\n Inorder : "); traverse(head); printf("\nMinorder : "); myt(head); getch(); }