fork(4) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
8
https://ideone.com/NkzPgJ
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!