Count of exponential paths in a Binary Tree | Python3 program to find the count exponential paths in Binary Tree ; Structure of a Tree node ; Function to create a new node ; Function to find x ; Take log10 of n ; Log ( n ) with base i ; Raising i to the power p ; Function to check whether the given node equals to x ^ y for some y > 0 ; Take logx ( n ) with base x ; Utility function to count the exponent path in a given Binary tree ; Base Condition , when node pointer becomes null or node value is not a number of pow ( x , y ) ; Increment count when encounter leaf node ; Left recursive call save the value of count ; Right recursive call and return value of count ; Function to count exponential paths ; Create Tree ; Retrieve the value of x ; Function call
import math NEW_LINE class Node : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . key = key NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def newNode ( key ) : NEW_LINE INDENT temp = Node ( key ) NEW_LINE return temp NEW_LINE DEDENT def find_x ( n ) : NEW_LINE INDENT if n == 1 : NEW_LINE INDENT return 1 NEW_LINE DEDENT num = math . log10 ( n ) NEW_LINE x , no = 0 , 0 NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT den = math . log10 ( i ) NEW_LINE p = num / den NEW_LINE no = int ( pow ( i , int ( p ) ) ) NEW_LINE if abs ( no - n ) < 1e-6 : NEW_LINE INDENT x = i NEW_LINE break NEW_LINE DEDENT DEDENT return x NEW_LINE DEDENT def is_key ( n , x ) : NEW_LINE INDENT p = math . log10 ( n ) / math . log10 ( x ) NEW_LINE no = int ( pow ( x , int ( p ) ) ) NEW_LINE if n == no : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT def evenPaths ( node , count , x ) : NEW_LINE INDENT if node == None or not is_key ( node . key , x ) : NEW_LINE INDENT return count NEW_LINE DEDENT if node . left == None and node . right == None : NEW_LINE INDENT count += 1 NEW_LINE DEDENT count = evenPaths ( node . left , count , x ) NEW_LINE return evenPaths ( node . right , count , x ) NEW_LINE DEDENT def countExpPaths ( node , x ) : NEW_LINE INDENT return evenPaths ( node , 0 , x ) NEW_LINE DEDENT root = newNode ( 27 ) NEW_LINE root . left = newNode ( 9 ) NEW_LINE root . right = newNode ( 81 ) NEW_LINE root . left . left = newNode ( 3 ) NEW_LINE root . left . right = newNode ( 10 ) NEW_LINE root . right . left = newNode ( 70 ) NEW_LINE root . right . right = newNode ( 243 ) NEW_LINE root . right . right . left = newNode ( 81 ) NEW_LINE root . right . right . right = newNode ( 909 ) NEW_LINE x = find_x ( root . key ) NEW_LINE print ( countExpPaths ( root , x ) ) NEW_LINE