Count of Fibonacci paths in a Binary tree | Vector to store the fibonacci series ; Binary Tree Node ; Function to create a new tree node ; Function to find the height of the given tree ; Function to make fibonacci series upto n terms ; Preorder Utility function to count 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 find whether fibonacci path exists or not ; To find the height ; Making fibonacci series upto ht terms ; Driver code ; Create binary tree ; Function Call
fib = [ ] NEW_LINE 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 newNode ( data ) : NEW_LINE INDENT temp = node ( data ) NEW_LINE return temp NEW_LINE DEDENT def height ( root ) : NEW_LINE INDENT ht = 0 NEW_LINE if ( root == None ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT return ( max ( height ( root . left ) , height ( root . right ) ) + 1 ) NEW_LINE DEDENT def FibonacciSeries ( n ) : NEW_LINE INDENT fib . append ( 0 ) NEW_LINE fib . append ( 1 ) NEW_LINE for i in range ( 2 , n ) : NEW_LINE INDENT fib . append ( fib [ i - 1 ] + fib [ i - 2 ] ) NEW_LINE DEDENT DEDENT def CountPathUtil ( root , i , count ) : NEW_LINE INDENT if ( root == None or not ( fib [ i ] == root . data ) ) : NEW_LINE INDENT return count NEW_LINE DEDENT if ( not root . left and not root . right ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT count = CountPathUtil ( root . left , i + 1 , count ) NEW_LINE return CountPathUtil ( root . right , i + 1 , count ) NEW_LINE DEDENT def CountPath ( root ) : NEW_LINE INDENT ht = height ( root ) NEW_LINE FibonacciSeries ( ht ) NEW_LINE print ( CountPathUtil ( root , 0 , 0 ) ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 0 ) NEW_LINE root . left = newNode ( 1 ) NEW_LINE root . right = newNode ( 1 ) NEW_LINE root . left . left = newNode ( 1 ) NEW_LINE root . left . right = newNode ( 4 ) NEW_LINE root . right . right = newNode ( 1 ) NEW_LINE root . right . right . left = newNode ( 2 ) NEW_LINE CountPath ( root ) NEW_LINE DEDENT