fork download
copy 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3.  
  4. /* A binary tree tNode has data, pointer to left child
  5.    and a pointer to right child */
  6. struct tNode
  7. {
  8.    int data;
  9.    struct tNode* left;
  10.    struct tNode* right;
  11. };
  12.  
  13.  
  14.  
  15. /* Function to traverse binary tree without recursion and
  16.    without stack */
  17. int MorrisRightToLeft(struct tNode *root,struct tNode **currCopy,struct tNode **prev)
  18. {
  19.   struct tNode *current,*pre;
  20.   int val;
  21.   if(root == NULL)
  22.      return;
  23.  
  24.   current = root;
  25.   if(*prev)
  26.   {
  27.      pre=*prev;
  28.   }
  29.   if(*currCopy)
  30.   {
  31.     current=*currCopy;
  32.   }
  33.   while(current != NULL)
  34.   { 
  35.     if(current->right == NULL)
  36.     {
  37.  
  38.       val=current->data;
  39.       current = current->left;
  40.       *prev=pre;
  41.       *currCopy=current;
  42.        return val;     
  43.     }   
  44.     else
  45.     {
  46.       /* Find the inorder predecessor of current */
  47.       pre = current->right;
  48.       while(pre->left != NULL && pre->left != current)
  49.         pre = pre->left;
  50.  
  51.       /* Make current as right child of its inorder predecessor */
  52.       if(pre->left == NULL)
  53.       {
  54.         pre->left = current;
  55.         current = current->right;
  56.       }
  57.  
  58.       /* Revert the changes made in if part to restore the original
  59.         tree i.e., fix the right child of predecssor */   
  60.       else 
  61.       {
  62.         pre->left = NULL;
  63.         val=current->data;
  64.         current = current->left;
  65. 	*prev=pre;
  66.       	*currCopy=current;
  67.        	return val;
  68.  
  69.       } /* End of if condition pre->right == NULL */
  70.     } /* End of if condition current->left == NULL*/
  71.   } /* End of while */
  72. return -1;
  73. }
  74.  
  75.  
  76. void MorrisLeftToRight(struct tNode *root,int N)
  77. {
  78.   struct tNode *current,*pre;
  79.   struct tNode *currCopy=NULL,*prev=NULL;
  80.   int l=0,r=0,label,label2; 
  81.   if(root == NULL)
  82.      return;
  83.  
  84.  
  85.   current = root;
  86.  
  87.   r= MorrisRightToLeft(root,&currCopy,&prev);
  88.   while(current != NULL)
  89.   { 
  90.     if(current->left == NULL)
  91.     {
  92.       		l =  current->data;
  93.  
  94. label1 :      	if(l!=r && l+r == N)
  95.       		{
  96.            		printf("\n\nSum1 found %d + %d = %d",l,r,N);
  97. 	   		return;
  98.       		}
  99.       		else if(l==r)
  100.       		{		
  101. 			printf("\n\nSum Does Not Exits");
  102. 			break;
  103.       		}
  104.       		else if(l + r > N)
  105.       		{
  106.             		r= MorrisRightToLeft(root,&currCopy,&prev);
  107. 	    		if(r==-1)
  108.             		{
  109. 				printf("\nCannot find sum\n");
  110. 				break;
  111.             		}
  112. 	    		goto label1;
  113. 	    		//continue;
  114.       		}
  115.       current = current->right;     
  116.     }   
  117.     else
  118.     {
  119.       /* Find the inorder predecessor of current */
  120.       pre = current->left;
  121.       while(pre->right != NULL && pre->right != current)
  122.         pre = pre->right;
  123.  
  124.       /* Make current as right child of its inorder predecessor */
  125.       if(pre->right == NULL)
  126.       {
  127.         pre->right = current;
  128.         current = current->left;
  129.       }
  130.  
  131.       /* Revert the changes made in if part to restore the original
  132.         tree i.e., fix the right child of predecssor */   
  133.       else 
  134.       {
  135.         	pre->right = NULL;
  136.         	l =  current->data;
  137. label2 : 	if(l!=r && l+r == N)
  138.         	{
  139. 			printf("\n\nSum2 found %d + %d = %d",l,r,N);
  140.                 	return;
  141.         	}
  142. 		else if(l==r)
  143.         	{
  144. 			printf("\n\nSum Does Not Exits");		
  145. 			break;
  146. 		}
  147.       		else if(l + r < N)
  148.       		{
  149.             		r= MorrisRightToLeft(root,&currCopy,&prev);
  150. 	    		if(r==-1)
  151.             		{
  152.                 		printf("\nCannot find sum\n");
  153.                 		break;
  154.             		}
  155. 			goto label2;
  156.          	//   continue;
  157.       		}
  158.         current = current->right;     
  159.       } /* End of if condition pre->right == NULL */
  160.     } /* End of if condition current->left == NULL*/
  161.   } /* End of while */
  162. }  
  163. /* UTILITY FUNCTIONS */
  164. /* Helper function that allocates a new tNode with the
  165.    given data and NULL left and right pointers. */
  166. struct tNode* newtNode(int data)
  167. {
  168.   struct tNode* tNode = (struct tNode*)
  169.                        malloc(sizeof(struct tNode));
  170.   tNode->data = data;
  171.   tNode->left = NULL;
  172.   tNode->right = NULL;
  173.  
  174.   return(tNode);
  175. }
  176.  
  177. /* Driver program to test above functions*/
  178. int main()
  179. {
  180.  
  181.   /* Constructed binary tree is
  182.             1
  183.           /   \
  184.         2      3
  185.       /  \
  186.     4     5
  187.   */
  188.   struct tNode *root = newtNode(50);
  189.   root->left        = newtNode(30);
  190.   root->right       = newtNode(55);
  191.   root->left->left  = newtNode(10);
  192.   root->left->right = newtNode(35);
  193.  int N=80;
  194.  
  195.   MorrisLeftToRight(root,N);
  196.   printf("\n\n");
  197.   return 0;
  198. }
  199.  
Success #stdin #stdout 0.01s 1852KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

Sum2 found 50 + 30 = 80
https://ideone.com/yp0jI
language:
C (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!