Find Count of Single Valued Subtrees | C ++ program to find count of single valued subtrees ; A Tree node ; Utility function to create a new node ; This function increments count by number of single valued subtrees under root . It returns true if subtree under root is Singly , else false . ; Return false to indicate NULL ; Recursively count in left and right subtrees also ; If any of the subtrees is not singly , then this cannot be singly . ; If left subtree is singly and non - empty , but data doesn 't match ; Same for right subtree ; If none of the above conditions is true , then tree rooted under root is single valued , increment count and return true . ; This function mainly calls countSingleRec ( ) after initializing count as 0 ; Initialize result ; Recursive function to count ; Driver program to test ; Let us construct the below tree 5 / \ 4 5 / \ \ 4 4 5
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * left , * right ; } ; Node * newNode ( int data ) { Node * temp = new Node ; temp -> data = data ; temp -> left = temp -> right = NULL ; return ( temp ) ; } bool countSingleRec ( Node * root , int & count ) { if ( root == NULL ) return true ; bool left = countSingleRec ( root -> left , count ) ; bool right = countSingleRec ( root -> right , count ) ; if ( left == false right == false ) return false ; if ( root -> left && root -> data != root -> left -> data ) return false ; if ( root -> right && root -> data != root -> right -> data ) return false ; count ++ ; return true ; } int countSingle ( Node * root ) { int count = 0 ; countSingleRec ( root , count ) ; return count ; } int main ( ) { Node * root = newNode ( 5 ) ; root -> left = newNode ( 4 ) ; root -> right = newNode ( 5 ) ; root -> left -> left = newNode ( 4 ) ; root -> left -> right = newNode ( 4 ) ; root -> right -> right = newNode ( 5 ) ; cout << " Count ▁ of ▁ Single ▁ Valued ▁ Subtrees ▁ is ▁ " << countSingle ( root ) ; return 0 ; }