Count of exponential paths in a Binary Tree | C # 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 ; Driver code ; Create Tree ; Retrieve the value of x ; Function call
using System ; class GFG { public class Node { public int key ; public Node left , right ; } static Node newNode ( int key ) { Node temp = new Node ( ) ; temp . key = key ; temp . left = temp . right = null ; return ( temp ) ; } static int find_x ( int n ) { if ( n == 1 ) return 1 ; double num , den , p ; num = Math . Log10 ( n ) ; int x = 0 , no = 0 ; for ( int i = 2 ; i <= n ; i ++ ) { den = Math . Log10 ( i ) ; p = num / den ; no = ( int ) ( Math . Pow ( i , ( int ) p ) ) ; if ( Math . Abs ( no - n ) < 0.000001 ) { x = i ; break ; } } return x ; } static bool is_key ( int n , int x ) { double p ; p = Math . Log10 ( n ) / Math . Log10 ( x ) ; int no = ( int ) ( Math . Pow ( x , ( int ) p ) ) ; if ( n == no ) return true ; return false ; } static int evenPaths ( Node node , int count , int x ) { if ( node == null || ! is_key ( node . key , x ) ) { return count ; } if ( node . left == null && node . right == null ) { count ++ ; } count = evenPaths ( node . left , count , x ) ; return evenPaths ( node . right , count , x ) ; } static int countExpPaths ( Node node , int x ) { return evenPaths ( node , 0 , x ) ; } public static void Main ( string [ ] args ) { 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 ) ; Console . Write ( countExpPaths ( root , x ) ) ; } }