fork(3) download
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. using namespace std;
  5.  
  6. // Tree node
  7. struct node
  8. {
  9. int data;
  10. struct node *left;
  11. struct node *right;
  12. };
  13.  
  14. //Utility function to create a tree node
  15. struct node *newNode(int k)
  16. {
  17. struct node *n=(struct node *)malloc(sizeof(struct node));
  18. n->left=NULL;
  19. n->right=NULL;
  20. n->data=k;
  21. return n;
  22. }
  23.  
  24. // Function takes a root node an integer pointer
  25. // which stores the total count of unival subtrees
  26. bool countOptimized_Util(struct node *root, int *counter)
  27. {
  28. if(!root)
  29. return true;
  30.  
  31. bool l=countOptimized_Util(root->left,counter);
  32. bool r=countOptimized_Util(root->right,counter);
  33.  
  34. // both left and right subtrees are unival
  35. if(l&&r)
  36. {
  37. struct node *rl=root->left;
  38. struct node *rr=root->right;
  39. // if leaf node
  40. if(!rl && !rr)
  41. {
  42. (*counter)++;
  43. return true;
  44. }
  45. // left and right child exists and their data is also same as root's data
  46. else if(rl && rr && rl->data==root->data && rr->data==root->data)
  47. {
  48. (*counter)++;
  49. return true;
  50. }
  51. // only left child exists and its data is same as root's data
  52. else if(rl && rl->data==root->data)
  53. {
  54. (*counter)++;
  55. return true;
  56. }
  57. // only right child exists and its data is same as root's data
  58. else if(rr && rr->data==root->data)
  59. {
  60. (*counter)++;
  61. return true;
  62. }
  63. }
  64. return false;
  65. }
  66.  
  67. // Counts the number of unival subtrees
  68. int countOptimized(struct node *root)
  69. {
  70. int counter=0;
  71. countOptimized_Util(root,&counter);
  72. return counter;
  73. }
  74.  
  75. // Driver function
  76. int main()
  77. {
  78.  
  79. struct node *root=NULL;
  80. root=newNode(1);
  81. root->left=newNode(2);
  82. root->left->left=newNode(2);
  83. root->left->right=newNode(2);
  84. root->left->left->left=newNode(5);
  85. root->left->left->right=newNode(5);
  86. root->right=newNode(3);
  87. root->right->left=newNode(3);
  88. root->right->right=newNode(3);
  89. root->right->left->left=newNode(4);
  90. root->right->left->right=newNode(4);
  91. root->right->right->left=newNode(3);
  92. root->right->right->right=newNode(3);
  93.  
  94. cout<<countOptimized(root);
  95. return 0;
  96. }
  97.  
Success #stdin #stdout 0s 3272KB
stdin
Standard input is empty
stdout
8