Define the Fibonacci binary tree of order n as follows If n0

Define the Fibonacci binary tree of order n as follows: If n=0 or n=1, the tree consists of a single node. If n>1, the tree consists of a root, with the Fibonacci tree of order n-1 as the left subtree and the Fibonacci tree of order n-2 as the right subtree. Write a method that builds a Fibonacci binary tree of order n and returns a pointer to it.

a) Is such a tree strictly binary?
b) What is the number of leaves in the Fibonacci tree of order n?
c) What is the depth of the Fibonacci tree of order n?

Solution

Method to build a Fibonacci binary tree of order of n:

node tree(int n){
node n = new node();
if (n == 0 || n == 1){
n.left = null;
n.right = null;
}
else {
n.left = tree(n-1);
n.right = tree(n-2);
}
return n;
}

a) Yes, the strictly binary tree when each node if it is not a leave has two children.

b) leaves in order n => if (n == 1 or n == 0) then 1
else number of leaves in order n = (number of leaves in order n-1) + (numer of leaves in order n-2)

c) Depth of the Fibonacci tree of order n => if n == 0 then depth is 1 else depth is n.