5.

(A) 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.

(B) Answer the following questions about Fibonacci binary tree defined in the previous problem.

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?

Write pseudo-code not Java for problems requiring code. You are responsible for the appropriate level of detail. For the questions asking for justification, please provide a detailed mathematically oriented discussion. A proof is not required.