Count of nodes in a Binary Tree whose child is its prime factors | Python program for Counting nodes whose immediate children are its factors ; To store all prime numbers ; Create a boolean array " prime [ 0 . . N ] " and initialize all its entries as true . A value in prime [ i ] will finally be false if i is Not a prime , else true . ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p greater than or equal to the square of it numbers which are multiples of p and are less than p ^ 2 are already marked . ; A Tree node ; Function to check if immediate children of a node are its factors or not ; Function to get the count of full Nodes in a binary tree ; If tree is empty ; Initialize count of full nodes having children as their factors ; If only right child exist ; If only left child exist ; Both left and right child exist ; Check for left child ; Check for right child ; Driver Code ; Create Binary Tree as shown ; To save all prime numbers ; Print Count of all nodes having children as their factors
from collections import deque NEW_LINE N = 1000000 NEW_LINE prime = [ ] NEW_LINE def SieveOfEratosthenes ( ) -> None : NEW_LINE INDENT check = [ True for _ in range ( N + 1 ) ] NEW_LINE p = 2 NEW_LINE while p * p <= N : NEW_LINE INDENT if ( check [ p ] ) : NEW_LINE INDENT prime . append ( p ) NEW_LINE for i in range ( p * p , N + 1 , p ) : NEW_LINE INDENT check [ i ] = False NEW_LINE DEDENT DEDENT p += 1 NEW_LINE DEDENT DEDENT class Node : NEW_LINE INDENT def __init__ ( self , key : int ) -> None : NEW_LINE INDENT self . key = key NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def IsChilrenPrimeFactor ( parent : Node , a : Node ) -> bool : NEW_LINE INDENT if ( prime [ a . key ] and ( parent . key % a . key == 0 ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT else : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT def GetCount ( node : Node ) -> int : NEW_LINE INDENT if ( not node ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT q = deque ( ) NEW_LINE count = 0 NEW_LINE q . append ( node ) NEW_LINE while q : NEW_LINE INDENT temp = q . popleft ( ) NEW_LINE if ( temp . left == None and temp . right != None ) : NEW_LINE INDENT if ( IsChilrenPrimeFactor ( temp , temp . right ) ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT if ( temp . right == None and temp . left != None ) : NEW_LINE INDENT if ( IsChilrenPrimeFactor ( temp , temp . left ) ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT if ( temp . left != None and temp . right != None ) : NEW_LINE INDENT if ( IsChilrenPrimeFactor ( temp , temp . right ) and IsChilrenPrimeFactor ( temp , temp . left ) ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT if ( temp . left != None ) : NEW_LINE INDENT q . append ( temp . left ) NEW_LINE DEDENT if ( temp . right != None ) : NEW_LINE INDENT q . append ( temp . right ) NEW_LINE DEDENT DEDENT return count NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT root = Node ( 10 ) NEW_LINE root . left = Node ( 2 ) NEW_LINE root . right = Node ( 5 ) NEW_LINE root . right . left = Node ( 18 ) NEW_LINE root . right . right = Node ( 12 ) NEW_LINE root . right . left . left = Node ( 2 ) NEW_LINE root . right . left . right = Node ( 3 ) NEW_LINE root . right . right . left = Node ( 3 ) NEW_LINE root . right . right . right = Node ( 14 ) NEW_LINE root . right . right . right . left = Node ( 7 ) NEW_LINE SieveOfEratosthenes ( ) NEW_LINE print ( GetCount ( root ) ) NEW_LINE DEDENT