fork(17) download
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define MAX_Q_SIZE 500
  4.  
  5. // A binary tree node
  6. struct node
  7. {
  8. int data;
  9. struct node *left, *right;
  10. };
  11.  
  12. // Queue related functions
  13. struct node** createQueue(int *, int *);
  14. void enQueue(struct node **, int *, struct node *);
  15. struct node *deQueue(struct node **, int *);
  16.  
  17. // An iterative method to find difference between
  18. int getLevelDiff(struct node *root)
  19. {
  20. if (root == NULL)
  21. return 0;
  22. int rear, front;
  23. struct node **queue = createQueue(&front, &rear);
  24. struct node *temp = root;
  25.  
  26. int level = 1, oddLevel_sum, evenLevel_sum;
  27. oddLevel_sum = evenLevel_sum = 0;
  28.  
  29. // A null value is used as a separator between two levels
  30. enQueue(queue, &rear, root);
  31. enQueue(queue, &rear, NULL);
  32.  
  33. // Do a level order traversal
  34. while (rear != front)
  35. {
  36. temp = deQueue(queue, &front);
  37.  
  38. // If this node is NULL, a new level is going to start
  39. if (temp == NULL)
  40. {
  41. // increment level number
  42. level++;
  43.  
  44. // insert a seperator if queue is not empty
  45. if (rear != front)
  46. enQueue(queue, &rear, NULL);
  47. }
  48. else // If this is from same level as previous node
  49. {
  50. if (level & 1)
  51. oddLevel_sum += temp->data;
  52. else
  53. evenLevel_sum += temp->data;
  54. if (temp->left)
  55. enQueue(queue, &rear, temp->left);
  56. if (temp->right)
  57. enQueue(queue, &rear, temp->right);
  58. }
  59. }
  60. return (oddLevel_sum - evenLevel_sum);
  61. }
  62.  
  63. struct node** createQueue(int *front, int *rear)
  64. {
  65. struct node **queue =
  66. (struct node **)malloc(sizeof(struct node*)*MAX_Q_SIZE);
  67.  
  68. *front = *rear = 0;
  69. return queue;
  70. }
  71.  
  72. void enQueue(struct node **queue, int *rear, struct node *new_node)
  73. {
  74. queue[*rear] = new_node;
  75. (*rear)++;
  76. }
  77.  
  78. struct node *deQueue(struct node **queue, int *front)
  79. {
  80. (*front)++;
  81. return queue[*front - 1];
  82. }
  83.  
  84. // A utility function to allocate a new tree node with given data
  85. struct node* newNode(int data)
  86. {
  87. struct node* node = (struct node*)malloc(sizeof(struct node));
  88. node->data = data;
  89. node->left = node->right = NULL;
  90. return (node);
  91. }
  92.  
  93. int main()
  94. {
  95. struct node *root = newNode(5);
  96. root->left = newNode(2);
  97. root->right = newNode(6);
  98. root->left->left = newNode(1);
  99. root->left->right = newNode(4);
  100. root->left->right->left = newNode(3);
  101. root->right->right = newNode(8);
  102. root->right->right->right = newNode(9);
  103. root->right->right->left = newNode(7);
  104. printf("%d is the required difference\n",getLevelDiff(root));
  105. return 0;
  106. }
  107.  
Success #stdin #stdout 0s 2428KB
stdin
Standard input is empty
stdout
-9 is the required difference