Count of Fibonacci paths in a Binary tree | C ++ 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 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > fib ; struct node { struct node * left ; int data ; struct node * right ; } ; node * newNode ( int data ) { node * temp = new node ; temp -> data = data ; temp -> left = NULL ; temp -> right = NULL ; return temp ; } int height ( node * root ) { int ht = 0 ; if ( root == NULL ) return 0 ; return ( max ( height ( root -> left ) , height ( root -> right ) ) + 1 ) ; } void FibonacciSeries ( int n ) { fib . push_back ( 0 ) ; fib . push_back ( 1 ) ; for ( int i = 2 ; i < n ; i ++ ) fib . push_back ( fib [ i - 1 ] + fib [ i - 2 ] ) ; } int CountPathUtil ( node * root , int i , int count ) { if ( root == NULL || ! ( fib [ i ] == root -> data ) ) { return count ; } if ( ! root -> left && ! root -> right ) { count ++ ; } count = CountPathUtil ( root -> left , i + 1 , count ) ; return CountPathUtil ( root -> right , i + 1 , count ) ; } void CountPath ( node * root ) { int ht = height ( root ) ; FibonacciSeries ( ht ) ; cout << CountPathUtil ( root , 0 , 0 ) ; } int main ( ) { 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 ) ; return 0 ; }