fork(18) download
copy 
  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.     getchar();
  106.     return 0;
  107. }
  108.  
Success #stdin #stdout 0s 2428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-9 is the required difference
https://ideone.com/845ZFY
language:
C (gcc 8.3)
created:
10 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!