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 Math . 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 ; Create binary tree ; Function Call
let fib = [ ] ; class node { constructor ( data ) { this . left = null ; this . right = null ; this . data = data ; } } ; function newNode ( data ) { let temp = new node ( data ) ; return temp ; } function height ( root ) { if ( root == null ) return 0 ; return ( Math . max ( height ( root . left ) , height ( root . right ) ) + 1 ) ; } function FibonacciSeries ( n ) { fib . push ( 0 ) ; fib . push ( 1 ) ; for ( let i = 2 ; i < n ; i ++ ) fib . push ( fib [ i - 1 ] + fib [ i - 2 ] ) ; } function CountPathUtil ( root , i , count ) { if ( root == null || ! ( fib [ i ] == root . data ) ) { return count ; } if ( root . left != null && root . right != null ) { count ++ ; } count = CountPathUtil ( root . left , i + 1 , count ) ; return CountPathUtil ( root . right , i + 1 , count ) ; } function CountPath ( root ) { let ht = height ( root ) ; FibonacciSeries ( ht ) ; document . write ( CountPathUtil ( root , 0 , 0 ) ) ; } let root = newNode ( 0 ) ; root . left = newNode ( 1 ) ; root . right = newNode ( 1 ) ; root . left . left = newNode ( 1 ) ; root . left . right = newNode ( 4 ) ; root . right . right = newNode ( 1 ) ; root . right . right . left = newNode ( 2 ) ; CountPath ( root ) ;