fork(2) 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 and an integer key.
  25. // Returns true if each node of tree rooted with 'root'
  26. // has same value equal to 'key' otherwise false
  27. bool isUnival_Util(struct node *root,int key)
  28. {
  29.     if(root==NULL)
  30.         return true;
  31.  
  32.     // if root's data and key are equal and left subtree 
  33.     // and right subtree are also unival
  34.     return (root->data==key && isUnival_Util(root->left,key) && isUnival_Util(root->right,key));
  35. }
  36.  
  37. // Tells whether tree is unival or not using a helper function
  38. bool isUnival(struct node *root)
  39. {
  40.     if(root==NULL)
  41.         return true;
  42.     int key=root->data;
  43.     return isUnival_Util(root,key);
  44. }
  45.  
  46. // Function takes a root node and an integer pointer
  47. // which stores the total count of unival subtrees
  48. void countUnivalsBF_Util(struct node *root, int *counter)
  49. {
  50.     if(!root)
  51.         return;
  52.  
  53.     if(isUnival(root))
  54.         (*counter)++;
  55.     countUnivalsBF_Util(root->left,counter);
  56.     countUnivalsBF_Util(root->right,counter);
  57. }
  58.  
  59. // Counts the number of unival subtrees
  60. int countUnivalsBF(struct node *root)
  61. {
  62.     int counter=0;
  63.     countUnivalsBF_Util(root,&counter);
  64.  
  65.     return counter;
  66. }
  67.  
  68. // Driver Function
  69. int main()
  70. {
  71.  
  72.     struct node *root=NULL;
  73.     root=newNode(1);
  74.     root->left=newNode(2);
  75.     root->left->left=newNode(2);
  76.     root->left->right=newNode(2);
  77.     root->left->left->left=newNode(5);
  78.     root->left->left->right=newNode(5);
  79.     root->right=newNode(3);
  80.     root->right->left=newNode(3);
  81.     root->right->right=newNode(3);
  82.     root->right->left->left=newNode(4);
  83.     root->right->left->right=newNode(4);
  84.     root->right->right->left=newNode(3);
  85.     root->right->right->right=newNode(3);
  86.  
  87.     cout<<countUnivalsBF(root);
  88.     return 0;
  89. }
Success #stdin #stdout 0s 3228KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
8
https://ideone.com/FVBgch
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!