Posted on by Kalkicode
Code Binary Tree

# Count of Fibonacci paths in a Binary tree

Here given code implementation process.

``````// C program
// Count of Fibonacci paths in a Binary tree

#include <stdio.h>
#include <stdlib.h>

//Binary Tree node
struct Node
{
int data;
struct Node *left, *right;
};

//This is creating a binary tree node and return this
struct Node *get_node(int data)
{
// Create dynamic node
struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
if (new_node != NULL)
{
//Set data and pointer values
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
//return new node
return new_node;
}

// Count all paths from root to leaf, which containing all fibonacci nodes
int count_fibonacci_path(struct Node*root,int a,int b)
{

if(root == NULL || a != root->data)
{
//When tree node is null or node not contain Fibonacci elements
return 0;
}
else
{
if(root->left==NULL && root->right == NULL)
{
//When get leaf node
return 1;
}
return count_fibonacci_path(root->left,b,a+b) + count_fibonacci_path(root->right,b,a+b);
}
}

int main()
{

struct Node *root = NULL;

/*
Construct Binary Tree
-----------------------
0
/   \
1      1
/ \    / \
1   1  1   1
/ \    / \   \
2   3  2   4   2
*/
root = get_node(0);
root->left = get_node(1);
root->right = get_node(1);
root->right->right = get_node(1);
root->left->right = get_node(1);
root->right->left = get_node(1);
root->left->left = get_node(1);
root->left->left->left = get_node(2);
root->left->left->right = get_node(3);
root->right->left->right = get_node(4);
root->right->left->left = get_node(2);
root->right->right->right = get_node(2);

int counter = count_fibonacci_path(root,0,1);

printf(" Fibonacci paths : %d \n",counter);

return 0;
}``````

#### Output

`` Fibonacci paths : 4``
``````/*
Java Program
Count of Fibonacci paths in a Binary tree
*/
//Binary Tree node
class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
//set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
public Node root;
public BinaryTree()
{
//Set initial tree root to null
this.root = null;
}
// Count all paths from root to leaf, which containing all fibonacci nodes
public int count_fibonacci_path(Node root, int a, int b)
{
if (root == null || a != root.data)
{
//When tree node is null or node not contain Fibonacci elements
return 0;
}
else
{
if (root.left == null && root.right == null)
{
//When get leaf node
return 1;
}
return count_fibonacci_path(root.left, b, a + b) + count_fibonacci_path(root.right, b, a + b);
}
}
public static void main(String[] args)
{
//Make object of binary tree
BinaryTree tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
0
/   \
1      1
/ \    / \
1   1  1   1
/ \    / \   \
2   3  2   4   2
*/
tree.root = new Node(0);
tree.root.left = new Node(1);
tree.root.right = new Node(1);
tree.root.right.right = new Node(1);
tree.root.left.right = new Node(1);
tree.root.right.left = new Node(1);
tree.root.left.left = new Node(1);
tree.root.left.left.left = new Node(2);
tree.root.left.left.right = new Node(3);
tree.root.right.left.right = new Node(4);
tree.root.right.left.left = new Node(2);
tree.root.right.right.right = new Node(2);
int counter = tree.count_fibonacci_path(tree.root, 0, 1);
// Display calculated result
System.out.print(" Fibonacci paths : " + counter + " \n");
}
}``````

#### Output

`` Fibonacci paths : 4``
``````//Include header file
#include <iostream>

using namespace std;
/*
C++ Program
Count of Fibonacci paths in a Binary tree
*/
//Binary Tree node
class Node
{
public: int data;
Node *left;
Node *right;
Node(int data)
{
//set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree
{
public: Node *root;
BinaryTree()
{
//Set initial tree root to null
this->root = NULL;
}
// Count all paths from root to leaf, which containing all fibonacci nodes
int count_fibonacci_path(Node *root, int a, int b)
{
if (root == NULL || a != root->data)
{
//When tree node is null or node not contain Fibonacci elements
return 0;
}
else
{
if (root->left == NULL && root->right == NULL)
{
//When get leaf node
return 1;
}
return this->count_fibonacci_path(root->left, b, a + b) + this->count_fibonacci_path(root->right, b, a + b);
}
}
};
int main()
{
//Make object of binary tree
BinaryTree tree = BinaryTree();
/*
Construct Binary Tree
-----------------------
0
/   \
1      1
/ \    / \
1   1  1   1
/ \    / \   \
2   3  2   4   2
*/
tree.root = new Node(0);
tree.root->left = new Node(1);
tree.root->right = new Node(1);
tree.root->right->right = new Node(1);
tree.root->left->right = new Node(1);
tree.root->right->left = new Node(1);
tree.root->left->left = new Node(1);
tree.root->left->left->left = new Node(2);
tree.root->left->left->right = new Node(3);
tree.root->right->left->right = new Node(4);
tree.root->right->left->left = new Node(2);
tree.root->right->right->right = new Node(2);
int counter = tree.count_fibonacci_path(tree.root, 0, 1);
// Display calculated result
cout << " Fibonacci paths : " << counter << " \n";
return 0;
}``````

#### Output

`` Fibonacci paths : 4``
``````//Include namespace system
using System;

/*
C# Program
Count of Fibonacci paths in a Binary tree
*/

//Binary Tree node
class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
//set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
public Node root;
public BinaryTree()
{
//Set initial tree root to null
this.root = null;
}
// Count all paths from root to leaf, which containing all fibonacci nodes
public int count_fibonacci_path(Node root, int a, int b)
{
if (root == null || a != root.data)
{
//When tree node is null or node not contain Fibonacci elements
return 0;
}
else
{
if (root.left == null && root.right == null)
{
//When get leaf node
return 1;
}
return count_fibonacci_path(root.left, b, a + b) + count_fibonacci_path(root.right, b, a + b);
}
}
public static void Main(String[] args)
{
//Make object of binary tree
BinaryTree tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
0
/   \
1      1
/ \    / \
1   1  1   1
/ \    / \   \
2   3  2   4   2
*/
tree.root = new Node(0);
tree.root.left = new Node(1);
tree.root.right = new Node(1);
tree.root.right.right = new Node(1);
tree.root.left.right = new Node(1);
tree.root.right.left = new Node(1);
tree.root.left.left = new Node(1);
tree.root.left.left.left = new Node(2);
tree.root.left.left.right = new Node(3);
tree.root.right.left.right = new Node(4);
tree.root.right.left.left = new Node(2);
tree.root.right.right.right = new Node(2);
int counter = tree.count_fibonacci_path(tree.root, 0, 1);
// Display calculated result
Console.Write(" Fibonacci paths : " + counter + " \n");
}
}``````

#### Output

`` Fibonacci paths : 4``
``````<?php
/*
Php Program
Count of Fibonacci paths in a Binary tree
*/

//Binary Tree node
class Node
{
public \$data;
public \$left;
public \$right;

function __construct(\$data)
{
//set node value
\$this->data = \$data;
\$this->left = null;
\$this->right = null;
}
}
class BinaryTree
{
public \$root;

function __construct()
{
//Set initial tree root to null
\$this->root = null;
}
// Count all paths from root to leaf, which containing all fibonacci nodes
public	function count_fibonacci_path(\$root, \$a, \$b)
{
if (\$root == null || \$a != \$root->data)
{
//When tree node is null or node not contain Fibonacci elements
return 0;
}
else
{
if (\$root->left == null && \$root->right == null)
{
//When get leaf node
return 1;
}
return \$this->count_fibonacci_path(\$root->left, \$b, \$a + \$b) + \$this->count_fibonacci_path(\$root->right, \$b, \$a + \$b);
}
}
}

function main()
{
//Make object of binary tree
\$tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
0
/   \
1      1
/ \    / \
1   1  1   1
/ \    / \   \
2   3  2   4   2
*/
\$tree->root = new Node(0);
\$tree->root->left = new Node(1);
\$tree->root->right = new Node(1);
\$tree->root->right->right = new Node(1);
\$tree->root->left->right = new Node(1);
\$tree->root->right->left = new Node(1);
\$tree->root->left->left = new Node(1);
\$tree->root->left->left->left = new Node(2);
\$tree->root->left->left->right = new Node(3);
\$tree->root->right->left->right = new Node(4);
\$tree->root->right->left->left = new Node(2);
\$tree->root->right->right->right = new Node(2);
\$counter = \$tree->count_fibonacci_path(\$tree->root, 0, 1);
// Display calculated result
echo " Fibonacci paths : ". \$counter ." \n";
}
main();``````

#### Output

`` Fibonacci paths : 4``
``````/*
Node Js Program
Count of Fibonacci paths in a Binary tree
*/

//Binary Tree node
class Node
{
constructor(data)
{
//set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
//Set initial tree root to null
this.root = null;
}
// Count all paths from root to leaf, which containing all fibonacci nodes
count_fibonacci_path(root, a, b)
{
if (root == null || a != root.data)
{
//When tree node is null or node not contain Fibonacci elements
return 0;
}
else
{
if (root.left == null && root.right == null)
{
//When get leaf node
return 1;
}
return this.count_fibonacci_path(root.left, b, a + b) + this.count_fibonacci_path(root.right, b, a + b);
}
}
}

function main()
{
//Make object of binary tree
var tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
0
/   \
1      1
/ \    / \
1   1  1   1
/ \    / \   \
2   3  2   4   2
*/
tree.root = new Node(0);
tree.root.left = new Node(1);
tree.root.right = new Node(1);
tree.root.right.right = new Node(1);
tree.root.left.right = new Node(1);
tree.root.right.left = new Node(1);
tree.root.left.left = new Node(1);
tree.root.left.left.left = new Node(2);
tree.root.left.left.right = new Node(3);
tree.root.right.left.right = new Node(4);
tree.root.right.left.left = new Node(2);
tree.root.right.right.right = new Node(2);
var counter = tree.count_fibonacci_path(tree.root, 0, 1);
// Display calculated result
process.stdout.write(" Fibonacci paths : " + counter + " \n");
}
main();``````

#### Output

`` Fibonacci paths : 4``
``````#   Python 3 Program
#   Count of Fibonacci paths in a Binary tree

# Binary Tree node
class Node :

def __init__(self, data) :
# set node value
self.data = data
self.left = None
self.right = None

class BinaryTree :

def __init__(self) :
# Set initial tree root to null
self.root = None

#  Count all paths from root to leaf, which containing all fibonacci nodes
def count_fibonacci_path(self, root, a, b) :
if (root == None or a != root.data) :
# When tree node is null or node not contain Fibonacci elements
return 0
else :
if (root.left == None and root.right == None) :
# When get leaf node
return 1

return self.count_fibonacci_path(root.left, b, a + b) + self.count_fibonacci_path(root.right, b, a + b)

def main() :
# Make object of binary tree
tree = BinaryTree()
#
# 		Construct Binary Tree
# 		-----------------------
# 		         0
# 		       /   \
# 		      1      1
# 		     / \    / \
# 		    1   1  1   1
# 		   / \    / \   \
# 		  2   3  2   4   2
#

tree.root = Node(0)
tree.root.left = Node(1)
tree.root.right = Node(1)
tree.root.right.right = Node(1)
tree.root.left.right = Node(1)
tree.root.right.left = Node(1)
tree.root.left.left = Node(1)
tree.root.left.left.left = Node(2)
tree.root.left.left.right = Node(3)
tree.root.right.left.right = Node(4)
tree.root.right.left.left = Node(2)
tree.root.right.right.right = Node(2)
counter = tree.count_fibonacci_path(tree.root, 0, 1)
#  Display calculated result
print(" Fibonacci paths : ", counter ," \n", end = "")

if __name__ == "__main__": main()``````

#### Output

`` Fibonacci paths :  4``
``````#   Ruby Program
#   Count of Fibonacci paths in a Binary tree

# Binary Tree node
class Node
# Define the accessor and reader of class Node
attr_accessor :data, :left, :right

def initialize(data)
# set node value
self.data = data
self.left = nil
self.right = nil
end

end

class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_accessor :root

def initialize()
# Set initial tree root to null
self.root = nil
end

#  Count all paths from root to leaf, which containing all fibonacci nodes
def count_fibonacci_path(root, a, b)
if (root == nil || a != root.data)
# When tree node is null or node not contain Fibonacci elements
return 0
else
if (root.left == nil && root.right == nil)
# When get leaf node
return 1
end

return self.count_fibonacci_path(root.left, b, a + b) + self.count_fibonacci_path(root.right, b, a + b)
end

end

end

def main()
# Make object of binary tree
tree = BinaryTree.new()
#
# 		Construct Binary Tree
# 		-----------------------
# 		         0
# 		       /   \
# 		      1      1
# 		     / \    / \
# 		    1   1  1   1
# 		   / \    / \   \
# 		  2   3  2   4   2
#

tree.root = Node.new(0)
tree.root.left = Node.new(1)
tree.root.right = Node.new(1)
tree.root.right.right = Node.new(1)
tree.root.left.right = Node.new(1)
tree.root.right.left = Node.new(1)
tree.root.left.left = Node.new(1)
tree.root.left.left.left = Node.new(2)
tree.root.left.left.right = Node.new(3)
tree.root.right.left.right = Node.new(4)
tree.root.right.left.left = Node.new(2)
tree.root.right.right.right = Node.new(2)
counter = tree.count_fibonacci_path(tree.root, 0, 1)
#  Display calculated result
print(" Fibonacci paths : ", counter ," \n")
end

main()``````

#### Output

`````` Fibonacci paths : 4
``````
``````/*
Scala Program
Count of Fibonacci paths in a Binary tree
*/

//Binary Tree node
class Node(var data: Int , var left: Node , var right: Node)
{
def this(data: Int)
{
this(data, null, null);
}
}
class BinaryTree(var root: Node)
{
def this()
{
this(null);
}
// Count all paths from root to leaf, which containing all fibonacci nodes
def count_fibonacci_path(root: Node, a: Int, b: Int): Int = {
if (root == null || a != root.data)
{
//When tree node is null or node not contain Fibonacci elements
return 0;
}
else
{
if (root.left == null && root.right == null)
{
//When get leaf node
return 1;
}
return count_fibonacci_path(root.left, b, a + b) + count_fibonacci_path(root.right, b, a + b);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
//Make object of binary tree
var tree: BinaryTree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
0
/   \
1      1
/ \    / \
1   1  1   1
/ \    / \   \
2   3  2   4   2
*/
tree.root = new Node(0);
tree.root.left = new Node(1);
tree.root.right = new Node(1);
tree.root.right.right = new Node(1);
tree.root.left.right = new Node(1);
tree.root.right.left = new Node(1);
tree.root.left.left = new Node(1);
tree.root.left.left.left = new Node(2);
tree.root.left.left.right = new Node(3);
tree.root.right.left.right = new Node(4);
tree.root.right.left.left = new Node(2);
tree.root.right.right.right = new Node(2);
var counter: Int = tree.count_fibonacci_path(tree.root, 0, 1);
// Display calculated result
print(" Fibonacci paths : " + counter + " \n");
}
}``````

#### Output

`` Fibonacci paths : 4``
``````/*
Swift 4 Program
Count of Fibonacci paths in a Binary tree
*/

//Binary Tree node
class Node
{
var data: Int;
var left: Node? ;
var right: Node? ;
init(_ data: Int)
{
//set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinaryTree
{
var root: Node? ;
init()
{
//Set initial tree root to null
self.root = nil;
}
// Count all paths from root to leaf, which containing all fibonacci nodes
func count_fibonacci_path(_ root: Node? , _ a : Int, _ b: Int)->Int
{
if (root == nil || a != root!.data)
{
//When tree node is null or node not contain Fibonacci elements
return 0;
}
else
{
if (root!.left == nil && root!.right == nil)
{
//When get leaf node
return 1;
}
return self.count_fibonacci_path(root!.left, b, a + b) + self.count_fibonacci_path(root!.right, b, a + b);
}
}
}
func main()
{
//Make object of binary tree
let tree: BinaryTree = BinaryTree();
/*
Construct Binary Tree
-----------------------
0
/   \
1      1
/ \    / \
1   1  1   1
/ \    / \   \
2   3  2   4   2
*/
tree.root = Node(0);
tree.root!.left = Node(1);
tree.root!.right = Node(1);
tree.root!.right!.right = Node(1);
tree.root!.left!.right = Node(1);
tree.root!.right!.left = Node(1);
tree.root!.left!.left = Node(1);
tree.root!.left!.left!.left = Node(2);
tree.root!.left!.left!.right = Node(3);
tree.root!.right!.left!.right = Node(4);
tree.root!.right!.left!.left = Node(2);
tree.root!.right!.right!.right = Node(2);
let counter: Int = tree.count_fibonacci_path(tree.root, 0, 1);
// Display calculated result
print(" Fibonacci paths : ", counter ," \n", terminator: "");
}
main();``````

#### Output

`` Fibonacci paths :  4``

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post