Skip to main content

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
*/
    //Add tree node
    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
		*/
		//Add tree node
		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
	*/
	//Add tree node
	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
				*/
		//Add tree node
		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
			*/
	//Add tree node
	$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
			*/
	//Add tree node
	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
	# 		
	
	# Add tree node
	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_reader :data, :left, :right
	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_reader :root
	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
	# 		
	
	# Add tree node
	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
				*/
		//Add tree node
		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
			*/
	//Add tree node
	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
Last updated on by Kalkicode




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.

New Comment