Count of Fibonacci paths in a Binary tree | Java program to count all 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 ; Driver code ; Create binary tree ; Function Call
import java . util . * ; class GFG { static Vector < Integer > fib = new Vector < Integer > ( ) ; static class node { node left ; int data ; node right ; } ; static node newNode ( int data ) { node temp = new node ( ) ; temp . data = data ; temp . left = null ; temp . right = null ; return temp ; } static int height ( node root ) { if ( root == null ) return 0 ; return ( Math . max ( height ( root . left ) , height ( root . right ) ) + 1 ) ; } static void FibonacciSeries ( int n ) { fib . add ( 0 ) ; fib . add ( 1 ) ; for ( int i = 2 ; i < n ; i ++ ) fib . add ( fib . get ( i - 1 ) + fib . get ( i - 2 ) ) ; } static int CountPathUtil ( node root , int i , int count ) { if ( root == null || ! ( fib . get ( 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 ) ; } static void CountPath ( node root ) { int ht = height ( root ) ; FibonacciSeries ( ht ) ; System . out . print ( CountPathUtil ( root , 0 , 0 ) ) ; } public static void main ( String [ ] args ) { node 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 ) ; } }