Define the Fibonacci binary tree of order n as follows: If n=0 or n=1, the tree

Question

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?

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.