1. The nth Fibonacci binary tree F is defined recursively as follows. F is a single...

 

Transcribed Image Text:

1. The nth Fibonacci binary tree F₁ is defined recursively as follows. F₁ is a single root node with no children. • For all n ≥ 2, Fn is obtained from F-1 by adding a right child to every leaf and adding a left child to every node that has only one child. Figure 1. The first six Fibonacci binary trees. In each tree F, the subtree of gray nodes is F-1. (b) Prove that the number of leaves in F is precisely the nth Fibonacci number: Fo = 0, F₁ = 1, and Fn = Fn-1 + Fn-2 for all n ≥ 2. (c) How many nodes does F₁ have? Given an exact closed-form answer in terms of Fibonacci numbers, and prove your answer is correct. (d) Prove that for all n ≥ 2, the right subtree of Fn is a copy of Fn-1. 1. The nth Fibonacci binary tree F₁ is defined recursively as follows. F₁ is a single root node with no children. • For all n ≥ 2, Fn is obtained from F-1 by adding a right child to every leaf and adding a left child to every node that has only one child. Figure 1. The first six Fibonacci binary trees. In each tree F, the subtree of gray nodes is F-1. (b) Prove that the number of leaves in F is precisely the nth Fibonacci number: Fo = 0, F₁ = 1, and Fn = Fn-1 + Fn-2 for all n ≥ 2. (c) How many nodes does F₁ have? Given an exact closed-form answer in terms of Fibonacci numbers, and prove your answer is correct. (d) Prove that for all n ≥ 2, the right subtree of Fn is a copy of Fn-1.

Answer rating: 100% (QA)

PAGE DATE th the a The numb... View the full answer