fork(2) download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int arrLen = 5;
  5. int maxdepth = 0;
  6. int mindepth = 10;
  7. int totalElem = 8;
  8.  
  9. typedef struct BST {
  10.     int data;
  11.     struct BST *left;
  12.     struct BST *right;
  13. } nodeBST;
  14.  
  15. void balanceBST(int arr[]);
  16. nodeBST* addNode(int data);
  17. void addNodeToBST(nodeBST *root, nodeBST *node);
  18. void traverse(nodeBST *root);
  19. void maxDepth(nodeBST *root, int depth);
  20. void minDepth(nodeBST *root, int depth);
  21.  
  22. int maxDepthWithoutGlobalVar(nodeBST *root, int depth, int maxDeep);
  23. int minDepthWithoutGlobalVar(nodeBST *root, int depth, int minDeep);
  24.  
  25. int main()
  26. {
  27.     int arr[10] = {5,3,7,10,6,12,2,1};
  28.  
  29.     (void)balanceBST(arr);
  30.  
  31.     return 0;
  32. }
  33.  
  34. void balanceBST(int arr[])
  35. {
  36.     nodeBST *node;
  37.     nodeBST *root;
  38.     int max = 0;
  39.     int min = 100000;
  40.     int i = 0;
  41.  
  42.     for (i = 0; i < totalElem; i++) {
  43. 	node = addNode(arr[i]);
  44. 	if (node == NULL) {
  45. 	    return;
  46. 	}
  47.  
  48. 	if (i == 0) {
  49. 	    root = node;
  50. 	    continue;
  51. 	}
  52.  
  53. 	addNodeToBST(root, node);
  54.     }
  55.  
  56.     printf("Nodes created\n");
  57.     traverse(root);
  58.     maxDepth(root, 0);
  59.     printf("\nMax Depth %d\n", maxdepth);
  60.     minDepth(root, 0);
  61.     printf("Min Depth %d\n\n", mindepth);
  62.  
  63.     max = maxDepthWithoutGlobalVar(root, 0, max);
  64.     printf("Max Depth %d\n", max);
  65.  
  66.     min = minDepthWithoutGlobalVar(root, 0, min);
  67.     printf("Min Depth %d\n", min);
  68.  
  69.     if ((max - min) > 1) {
  70. 	printf("Binary search tree is not Balanced\n");
  71.     } else {
  72. 	printf("Binary search tree is Balanced\n");
  73.     }
  74. }
  75.  
  76. nodeBST* addNode(int data)
  77. {
  78.     nodeBST *node = (nodeBST*)calloc(1, sizeof(nodeBST));
  79.  
  80.     if (node == NULL) {
  81. 	return NULL;
  82.     }
  83.  
  84.     node->data = data;
  85.     node->left = NULL;
  86.     node->right = NULL;
  87.  
  88.     return node;
  89. }
  90.  
  91. void addNodeToBST(nodeBST *root, nodeBST *node)
  92. {
  93.     while(root != NULL) {
  94. 	if (node->data < root->data) {
  95. 	    if (root->left != NULL) {
  96. 		root = root->left;
  97. 	    } else {
  98. 		root->left = node;
  99. 		return;
  100. 	    }
  101. 	} else {
  102. 	    if (root->right != NULL) {
  103. 		root = root->right;
  104. 	    } else {
  105. 		root->right = node;
  106. 		return;
  107. 	    }
  108. 	}
  109.     }
  110.  
  111.     return;
  112. }
  113.  
  114. void traverse(nodeBST *root)
  115. {
  116.     if (root == NULL) {
  117. 	return;
  118.     } else {
  119. 	traverse(root->left);
  120. 	printf("%d ", root->data);
  121. 	traverse(root->right);
  122.     }
  123.  
  124.     return;
  125. }
  126.  
  127. void maxDepth(nodeBST *root, int depth)
  128. {
  129.     if (root == NULL) {
  130. 	if (maxdepth < depth) {
  131. 	    maxdepth = depth;
  132. 	}
  133.     } else {
  134. 	maxDepth(root->left, (depth + 1));
  135. 	maxDepth(root->right, (depth + 1));
  136.     }
  137. }
  138.  
  139. void minDepth(nodeBST *root, int depth)
  140. {
  141.     if (root == NULL) {
  142. 	if (mindepth > depth) {
  143. 	    mindepth = depth;
  144. 	}
  145.     } else {
  146. 	minDepth(root->left, (depth + 1));
  147. 	minDepth(root->right, (depth + 1));
  148.     }
  149. }
  150.  
  151. int maxDepthWithoutGlobalVar(nodeBST *root, int depth, int maxDeep)
  152. {
  153.     if (root == NULL) {
  154. 	if (maxDeep <= depth) {
  155. 	    maxDeep = depth;
  156. 	}
  157. 	return maxDeep;
  158.     } else {
  159.         maxDeep = maxDepthWithoutGlobalVar(root->left, (depth + 1), maxDeep);
  160. 	maxDeep = maxDepthWithoutGlobalVar(root->right, (depth + 1), maxDeep);
  161.     }
  162.  
  163.     return maxDeep;
  164. }
  165.  
  166. int minDepthWithoutGlobalVar(nodeBST *root, int depth, int minDeep)
  167. {
  168.     if (root == NULL) {
  169. 	if (minDeep >= depth) {
  170. 	    minDeep = depth;
  171. 	}
  172. 	return minDeep;
  173.     } else {
  174.         minDeep = minDepthWithoutGlobalVar(root->left, (depth + 1), minDeep);
  175. 	minDeep = minDepthWithoutGlobalVar(root->right, (depth + 1), minDeep);
  176.     }
  177.  
  178.     return minDeep;
  179. }
  180.  
  181.  
Success #stdin #stdout 0s 2424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Nodes created
1 2 3 5 6 7 10 12 
Max Depth 4
Min Depth 2

Max Depth 4
Min Depth 2
Binary search tree is not Balanced
https://ideone.com/2rEls9
Find BST is Balanced
language:
C (gcc 8.3)
created:
10 years ago
visibility:
secret

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!