The Calkin-Wilf tree is a complete binary tree. The tree is rooted at the number 1, and any rational number expressed in simplest terms as the fraction $\frac{a}{b}$ has as its two children the numbers $\frac{a}{a+b}$ and $\frac{a+b}{b}$. Every positive rational number appears exactly once in the tree.

• Give all the declaration needed to declare such a tree.

• Write a recursive function that, given a height $h$, creates and returns a Calkin-Wilf tree of height $h$.

• The Calkin-Wilf sequence is the sequence of rational numbers generated by a level-order traversal of the Calkin-Wilf tree. Since the Calkin-Wilf tree contains every positive rational number exactly once, so does this sequence. The denominator of each fraction equals the numerator of the next fraction in the sequence.
  Write an iterative function that, given a tree, performs the level-order traversal and checks whether the denominator of each fraction equals the numerator of the next fraction in the sequence. 

As a reminder, in the postorder traversal of a binary tree, traverse the left subtree, then traverse the right subtree, then visit the root. However in the reverse postorder traversal of a binary tree, traverse the right subtree, then the left subtree, and then visit the root.

• Write a recursive function that performs the postorder traversal of a binary tree.
• Write a recursive function that performs the reverse postorder traversal of a binary tree.
• Write on one line the output of the postorder traversal, and on a second line the output of the reverse postorder traversal of the Calkin-Wilf tree shown above. Deduce.
• Given a tree $T$, write an iterative function that returns true if $T$ is the Calkin-Wilf tree, otherwise return false.
  Expected time complexity is $O(n)$, where $n$ is the number of nodes. Any modification to the tree is not allowed.
  Method: traverse the tree in postorder and reverse postorder simultaneously. Compare current nodes in both traversals. If a mismatch appears returns false, otherwise proceed till you reach the node containing the fraction $\frac{1}{1}$ and then return 1.

*************************************************************

typedef struct{
    int num;
    int denum;
} element;

typedef struct node
{
	element data;
	struct node *left,*right;
} *Btree;

*************************************************************

void CreateCalkinWilfTree_h(Btree *B, int numerator, int denumerator, int height)
{
     
    if(height>0)
    {
         *B=(Btree) malloc(sizeof(struct node));
         (*B)->data.num=numerator;
         (*B)->data.denum=denumerator;
         CreateCalkinWilfTree_h(&((*B)->left), numerator,  
                                      numerator + denumerator, height-1);
          CreateCalkinWilfTree_h(&((*B)->right), 
                          numerator + denumerator, denumerator, height-1);
    }
}

Btree CreateCalkinWilfTree(int height)
{
    Btree B=NULL;
    CreateCalkinWilfTree_h(&B, 1 , 1, height);
    return B;
}

*************************************************************

int levelorder(Btree B)
{
	queue q = CreateQueue();
	Btree temp;
	int denum;

	if(B==NULL) return 0;

	EnQueue(&q,B);
       denum=B->data.denum;
	while(Front(q,&temp))
	{
		DeQueue(&q);
		if(denum!=temp->data.num)
		    return 0;
		denum = temp->data.denum;
		if(temp->left != NULL)
			EnQueue(&q,temp->left);
		if(temp->right != NULL)
			EnQueue(&q,temp->right);
	}
	return 1;
}

*************************************************************

void postorder(Btree B)
{
    if(B)
    {
        postorder(B->left);
        postorder(B->right);
        printf("%d/%d ",B->data.num,B->data.denum);
    }
} 

*************************************************************

void postorderrev(Btree B)
{
    if(B)
    {
        postorderrev (B->right);
        postorderrev (B->left);
        printf("%d/%d ",B->data.num,B->data.denum);
    }
}

*************************************************************

postorder
1/4 4/3 1/3 3/5 5/2 3/2 1/2 2/5 5/3 2/3 3/4 4/1 3/1 2/1 1/1 

postorder rev
4/1 3/4 3/1 5/3 2/5 2/3 2/1 5/2 3/5 3/2 4/3 1/4 1/3 1/2 1/1 

Each fraction in the postorder traversal is reversed in the same position in the reverse postorder traversal

*************************************************************

int check (Btree B)
{
    stack s1 = CreateStack();
    stack s2 = CreateStack(); 
    int done1 = 0, done2 = 0;
    element val1, val2;
    Btree curr1 = B, curr2 = B;
    Btree previous1 = NULL, previous2 = NULL;

    while (1)
    {
        while (done1 == 0)
        {
               while(curr1 != NULL) {
			    Push(&s1,curr1);
			    curr1=curr1->left; 
               }
		if(!isEmptyStack(s1))
		 {
			    Top(s1,&curr1);
			    if(curr1->right==NULL || curr1->right==previous1)
			    {
			           val1 = curr1->data;
				    previous1=curr1;
				    curr1 = NULL;
				    Pop(&s1);
				    done1=1;
			    }
			    else
				    curr1=curr1->right;
		    }
		    else
			    done1=1;
        }
        
        while (done2 == 0)
        {
                  while(curr2 != NULL) {
			    Push(&s2,curr2);
			    curr2=curr2->right; 
                   }
		    if(!isEmptyStack(s2))
		    {
			    Top(s2,&curr2);
			    if(curr2->left==NULL || curr2->left==previous2)
			    {
			           val2 = curr2->data;
				    previous2=curr2;
				    curr2 = NULL;
				    Pop(&s2);
				    done2=1;
			    }
			    else
				    curr2=curr2->left;
		    }
		    else
			    done2=1;
        }
        
        if (val1.num == val2.num && val1.denum == val2.denum 
                && val1.num == 1 && val1.denum==1)
            return 1;
        if(val1.num!=val2.denum || val2.num!=val1.denum )
            return 0;
        done1=0;
        done2=0;
    }
}

*************************************************************