Find Count of Single Valued Subtrees | 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 None ; Recursively count in left and right subtress also ; If any of the subtress 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 calss countSingleRec ( ) after initializing count as 0 ; initialize result ; Recursive function to count ; Let us construct the below tree 5 / \ 4 5 / \ \ 4 4 5
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def countSingleRec ( root , count ) : NEW_LINE INDENT if root is None : NEW_LINE INDENT return True NEW_LINE DEDENT left = countSingleRec ( root . left , count ) NEW_LINE right = countSingleRec ( root . right , count ) NEW_LINE if left == False or right == False : NEW_LINE INDENT return False NEW_LINE DEDENT if root . left and root . data != root . left . data : NEW_LINE INDENT return False NEW_LINE DEDENT if root . right and root . data != root . right . data : NEW_LINE INDENT return False NEW_LINE DEDENT count [ 0 ] += 1 NEW_LINE return True NEW_LINE DEDENT def countSingle ( root ) : NEW_LINE INDENT count = [ 0 ] NEW_LINE countSingleRec ( root , count ) NEW_LINE return count [ 0 ] NEW_LINE DEDENT root = Node ( 5 ) NEW_LINE root . left = Node ( 4 ) NEW_LINE root . right = Node ( 5 ) NEW_LINE root . left . left = Node ( 4 ) NEW_LINE root . left . right = Node ( 4 ) NEW_LINE root . right . right = Node ( 5 ) NEW_LINE countSingle ( root ) NEW_LINE print " Count ▁ of ▁ Single ▁ Valued ▁ Subtress ▁ is " , countSingle ( root ) NEW_LINE