Count of exponential paths in a Binary Tree | C ++ program to find the count exponential paths in Binary Tree ; 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 ; Driver Code ; create Tree ; retrieve the value of x ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int key ; struct Node * left , * right ; } ; Node * newNode ( int key ) { Node * temp = new Node ; temp -> key = key ; temp -> left = temp -> right = NULL ; return ( temp ) ; } int find_x ( int n ) { if ( n == 1 ) return 1 ; double num , den , p ; num = log10 ( n ) ; int x , no ; for ( int i = 2 ; i <= n ; i ++ ) { den = log10 ( i ) ; p = num / den ; no = ( int ) ( pow ( i , int ( p ) ) ) ; if ( abs ( no - n ) < 1e-6 ) { x = i ; break ; } } return x ; } bool is_key ( int n , int x ) { double p ; p = log10 ( n ) / log10 ( x ) ; int no = ( int ) ( pow ( x , int ( p ) ) ) ; if ( n == no ) return true ; return false ; } int evenPaths ( struct Node * node , int count , int x ) { if ( node == NULL || ! is_key ( node -> key , x ) ) { return count ; } if ( ! node -> left && ! node -> right ) { count ++ ; } count = evenPaths ( node -> left , count , x ) ; return evenPaths ( node -> right , count , x ) ; } int countExpPaths ( struct Node * node , int x ) { return evenPaths ( node , 0 , x ) ; } int main ( ) { Node * root = newNode ( 27 ) ; root -> left = newNode ( 9 ) ; root -> right = newNode ( 81 ) ; root -> left -> left = newNode ( 3 ) ; root -> left -> right = newNode ( 10 ) ; root -> right -> left = newNode ( 70 ) ; root -> right -> right = newNode ( 243 ) ; root -> right -> right -> left = newNode ( 81 ) ; root -> right -> right -> right = newNode ( 909 ) ; int x = find_x ( root -> key ) ; cout << countExpPaths ( root , x ) ; return 0 ; }