fork(1) download
copy 
  1. #include<stdio.h>
  2. #include<malloc.h>
  3.  
  4. struct binaryTreeNode{
  5. 	int data;
  6. 	struct binaryTreeNode * left;
  7. 	struct binaryTreeNode * right;
  8. };
  9.  
  10. struct node
  11. {
  12. 	struct binaryTreeNode * data;
  13. 	struct node * next;
  14. };
  15.  
  16. struct queue
  17. {
  18. 	struct node * front;
  19. 	struct node * rear;
  20. };
  21.  
  22. struct queue * enQueue(struct queue * q, struct binaryTreeNode * num)
  23. {
  24. 	struct node * temp = (struct node*)malloc(sizeof(struct node));
  25. 	temp -> data = num;
  26. 	temp -> next = NULL;
  27. 	if(q == NULL)
  28. 	{
  29. 		q = (struct queue*)malloc(sizeof(struct queue));		
  30. 		q -> front = temp;
  31. 	}
  32. 	else
  33. 		q -> rear -> next = temp;
  34. 	q -> rear = temp;
  35. 	//Code obtained from http://w...content-available-to-author-only...w.studyalgorithms,com
  36. 	//Feel free to copy but please acknowledge the site wherever possible
  37. 	return q;
  38. }
  39.  
  40. struct queue * deQueue(struct queue * q)
  41. {
  42. 	struct node * temp = q->front;
  43. 	q -> front = q->front->next;
  44. 	free(temp);
  45. 	if(q->front == NULL)
  46. 		return NULL;
  47. 	else
  48. 		return q;
  49. }
  50.  
  51. int isQueueEmpty(struct queue * q)
  52. {
  53. 	if(q)
  54. 		return 0;
  55. 	else
  56. 		return 1;
  57. }
  58.  
  59. int findElementInTreeRecursive(struct binaryTreeNode * root, int num)
  60. {
  61. 	// A variable for root value
  62. 	int root_val;
  63.  
  64. 	// Variable to store values in left and right tree
  65. 	int left, right;
  66.  
  67. 	if(root != NULL)
  68. 	{
  69. 		// Get the root value
  70. 		root_val = root -> data;
  71.  
  72. 		if(root_val == num)
  73. 			return 1;
  74.  
  75. 		// Find the element in left sub-tree
  76. 		// If found, we return 1
  77. 		left = findElementInTreeRecursive(root -> left, num);
  78. 		if(left == 1)
  79. 			return 1;
  80. 		else
  81. 		{
  82. 			// We need to find the element in right sub-tree
  83. 			right = findElementInTreeRecursive(root -> right, num);
  84. 			if(right == 1)
  85. 				return 1;
  86. 		}
  87. 	}
  88.  
  89. 	// If we reach here, that means the element was not found
  90. 	return 0;
  91. }
  92.  
  93. int findElementInTreeNonRecursive(struct binaryTreeNode * root, int num)
  94. {
  95. 	int found = 0;
  96.  
  97. 	// Level Order Traversal
  98. 	struct binaryTreeNode * temp = NULL;
  99. 	struct queue * Q = NULL;
  100. 	if(root == NULL)
  101. 		return;
  102.  
  103. 	Q = enQueue(Q, root);
  104.  
  105. 	while(!isQueueEmpty(Q))
  106. 	{
  107. 		temp = Q -> front -> data;
  108.  
  109. 		Q = deQueue(Q);
  110.  
  111. 		// Find the element
  112. 		if(temp -> data == num)
  113. 		{
  114. 			found = 1;
  115. 			break;
  116. 		}
  117.  
  118. 		if(temp -> left)
  119. 			Q = enQueue(Q, temp -> left);
  120. 		if(temp -> right)
  121. 			Q = enQueue(Q, temp -> right);
  122. 	}
  123. 	free(Q);
  124.  
  125. 	// Return 1 if element was found
  126. 	return found;
  127. }
  128.  
  129. // Test the above functions
  130. int main(void)
  131. {
  132. 	// Initialize the tree
  133. 	struct binaryTreeNode * root = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
  134. 	root-> data = 1;
  135. 	struct binaryTreeNode * l = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
  136. 	l -> data = 2;
  137. 	struct binaryTreeNode * ll = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
  138. 	ll -> data = 4;
  139. 	ll -> left = ll -> right = NULL;
  140. 	struct binaryTreeNode * lr = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
  141. 	lr -> data = 5;
  142. 	lr -> left = lr -> right = NULL;
  143. 	l -> left = ll;
  144. 	l -> right = lr;
  145. 	struct binaryTreeNode * r = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
  146. 	r -> data = 3;
  147. 	struct binaryTreeNode * rl = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
  148. 	rl -> data = 6;
  149. 	rl -> left = rl -> right = NULL;
  150. 	struct binaryTreeNode * rr = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
  151. 	rr -> data = 7;
  152. 	rr -> left = rr -> right = NULL;
  153. 	r -> left = rl;
  154. 	r -> right = rr;
  155. 	root -> left = l;
  156. 	root -> right = r;
  157.  
  158. 	// recursive version
  159. 	if(findElementInTreeRecursive(root, 90))
  160. 		printf("PRESENT");
  161. 	else
  162. 		printf("NOT PRESENT");
  163.  
  164. 	printf("\n");
  165.  
  166. 	// Non-recursive version
  167. 	if(findElementInTreeNonRecursive(root, 90))
  168. 		printf("PRESENT");
  169. 	else
  170. 		printf("NOT PRESENT");
  171.  
  172. 	return 0;
  173. }
Success #stdin #stdout 0s 2424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
NOT PRESENT
NOT PRESENT
https://ideone.com/tzK8CJ
language:
C (gcc 8.3)
created:
9 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!