Given a number K, the task is to print the fibonacci numbers present at Kth level of a Fibonacci Binary Tree.
Examples:
Input: K = 3
Output: 2, 3, 5, 8
Explanation:
Fibonacci Binary Tree for 3 levels:
0
/ \
1 1
/\ / \
2 3 5 8
Numbers present at level 3: 2, 3, 5, 8
Input: K = 2
Output: 1, 1
Explanation:
Fibonacci Binary Tree for 2 levels:
0
/ \
1 1
Numbers present at level 2: 1, 1
Naive Approach: The naive approach is to build a Fibonacci Binary Tree (binary tree of Fibonacci numbers) and then get elements at a particular level K.
However, this approach is obsolete for large numbers as it takes too much time.
Efficient approach: Since the elements which would be present at some arbitrary level K of the tree can be found by finding the elements in the range [2K – 1, 2K – 1]. Therefore:
- Find the Fibonacci numbers up to 106 using Dynamic Programming and store them in an array.
- Calculate the left_index and right_index of the level as:
left_index = 2K - 1 right_index = 2K - 1
- Print the fibonacci numbers from left_index to right_index of fibonacci array.
Below is the implementation of the above approach:
C++
// C++ program to print the Fibonacci numbers// present at K-th level of a Binary Tree#include <bits/stdc++.h>using namespace std;// Initializing the max value#define MAX_SIZE 100005// Array to store all the// fibonacci numbersint fib[MAX_SIZE + 1];// Function to generate fibonacci numbers// using Dynamic Programmingvoid fibonacci(){ int i; // 0th and 1st number of the series // are 0 and 1 fib[0] = 0; fib[1] = 1; for (i = 2; i <= MAX_SIZE; i++) { // Add the previous two numbers in the // series and store it fib[i] = fib[i - 1] + fib[i - 2]; }}// Function to print the Fibonacci numbers// present at Kth level of a Binary Treevoid printLevel(int level){ // Finding the left and right index int left_index = pow(2, level - 1); int right_index = pow(2, level) - 1; // Iterating and printing the numbers for (int i = left_index; i <= right_index; i++) { cout << fib[i - 1] << " "; } cout << endl;}// Driver codeint main(){ // Precomputing Fibonacci numbers fibonacci(); int K = 4; printLevel(K); return 0;} |
Java
// Java program to print the Fibonacci numbers// present at K-th level of a Binary Treeimport java.util.*;class GFG{ // Initializing the max valuestatic final int MAX_SIZE = 100005; // Array to store all the// fibonacci numbersstatic int []fib = new int[MAX_SIZE + 1]; // Function to generate fibonacci numbers// using Dynamic Programmingstatic void fibonacci(){ int i; // 0th and 1st number of the series // are 0 and 1 fib[0] = 0; fib[1] = 1; for (i = 2; i <= MAX_SIZE; i++) { // Add the previous two numbers in the // series and store it fib[i] = fib[i - 1] + fib[i - 2]; }} // Function to print the Fibonacci numbers// present at Kth level of a Binary Treestatic void printLevel(int level){ // Finding the left and right index int left_index = (int) Math.pow(2, level - 1); int right_index = (int) (Math.pow(2, level) - 1); // Iterating and printing the numbers for (int i = left_index; i <= right_index; i++) { System.out.print(fib[i - 1]+ " "); } System.out.println();} // Driver codepublic static void main(String[] args){ // Precomputing Fibonacci numbers fibonacci(); int K = 4; printLevel(K);}}// This code is contributed by Rajput-Ji |
Python3
# Python program to print the Fibonacci numbers# present at K-th level of a Binary Tree# Initializing the max valueMAX_SIZE = 100005# Array to store all the# fibonacci numbersfib =[0]*(MAX_SIZE + 1)# Function to generate fibonacci numbers# using Dynamic Programmingdef fibonacci(): # 0th and 1st number of the series # are 0 and 1 fib[0] = 0 fib[1] = 1 for i in range(2, MAX_SIZE + 1): # Add the previous two numbers in the # series and store it fib[i] = fib[i - 1] + fib[i - 2] # Function to print the Fibonacci numbers# present at Kth level of a Binary Treedef printLevel(level): # Finding the left and right index left_index = pow(2, level - 1) right_index = pow(2, level) - 1 # Iterating and printing the numbers for i in range(left_index, right_index+1): print(fib[i - 1],end=" ") print()# Driver code# Precomputing Fibonacci numbersfibonacci()K = 4printLevel(K)# This code is contributed by shivanisinghss2110 |
C#
// C# program to print the Fibonacci numbers // present at K-th level of a Binary Tree using System;class GFG{ // Initializing the max value static int MAX_SIZE = 100005; // Array to store all the // fibonacci numbers static int []fib = new int[MAX_SIZE + 1]; // Function to generate fibonacci numbers // using Dynamic Programming static void fibonacci() { int i; // 0th and 1st number of the series // are 0 and 1 fib[0] = 0; fib[1] = 1; for (i = 2; i <= MAX_SIZE; i++) { // Add the previous two numbers in the // series and store it fib[i] = fib[i - 1] + fib[i - 2]; } } // Function to print the Fibonacci numbers // present at Kth level of a Binary Tree static void printLevel(int level) { // Finding the left and right index int left_index = (int) Math.Pow(2, level - 1); int right_index = (int) (Math.Pow(2, level) - 1); // Iterating and printing the numbers for (int i = left_index; i <= right_index; i++) { Console.Write(fib[i - 1]+ " "); } Console.WriteLine(); } // Driver code public static void Main(string[] args) { // Precomputing Fibonacci numbers fibonacci(); int K = 4; printLevel(K); } } // This code is contributed by Yash_R |
Javascript
<script>// Javascript program to print the Fibonacci numbers// present at K-th level of a Binary Tree // Initializing the max value var MAX_SIZE = 100005; // Array to store all the // fibonacci numbers var fib = Array(MAX_SIZE + 1).fill(0); // Function to generate fibonacci numbers // using Dynamic Programming function fibonacci() { var i; // 0th and 1st number of the series // are 0 and 1 fib[0] = 0; fib[1] = 1; for (i = 2; i <= MAX_SIZE; i++) { // Add the previous two numbers in the // series and store it fib[i] = fib[i - 1] + fib[i - 2]; } } // Function to print the Fibonacci numbers // present at Kth level of a Binary Tree function printLevel(level) { // Finding the left and right index var left_index = parseInt( Math.pow(2, level - 1)); var right_index = parseInt( (Math.pow(2, level) - 1)); // Iterating and printing the numbers for (i = left_index; i <= right_index; i++) { document.write(fib[i - 1] + " "); } document.write(); } // Driver code // Precomputing Fibonacci numbers fibonacci(); var K = 4; printLevel(K);// This code contributed by umadevi9616 </script> |
Output:
13 21 34 55 89 144 233 377
Time complexity : O(MAX_SIZE)
Auxiliary space : O(MAX_SIZE)
Efficient approach :
Space optimization O(1)
In previous approach the fib[i] is depend upon fib[i-1] and fib[i-2] So to calculate the current value we just need two previous values. In this approach we replace fib[i-1] to prev1 and fib[i-2] to prev2 and fib[i] to curr.
Steps that were to follow this approach:
- Initialize variables prev1, prev2 and curr to keep track of previous two values and current value.
- Set base cases of prev1 and prev2.
- Iterate over subproblems and get the current value and store in curr.
- After every iteration store prev2 to prev1 and curr to prev2 to iterate further.
- At last iterate every computation and print curr.
Below is the code to implement the above approach:
C++
// C++ program to print the Fibonacci numbers// present at K-th level of a Binary Tree#include <bits/stdc++.h>using namespace std;// Function to generate fibonacci numbers// using Dynamic Programmingvoid printFibonacciLevel(int level) { // initialize previous and current values int prev1 = 0, prev2 = 1; int curr; // left most index int left_index = pow(2, level - 1); for (int i = 1; i <= left_index; i++) { // compute curr if (i <= 2) { curr = i - 1; } else { curr = prev1 + prev2; // assigning values prev1 = prev2; prev2 = curr; } } // right most index int right_index = pow(2, level) - 2; for (int i = left_index; i <= right_index+1; i++) { cout << curr << " "; // compute curr if (i <= 2) { curr = i - 1; } else { curr = prev1 + prev2; // assigning values prev1 = prev2; prev2 = curr; } } cout << endl;}// Driver Codeint main() { int K = 4; // function call printFibonacciLevel(K); return 0;} |
Java
// Java program to print the Fibonacci numbers// present at K-th level of a Binary Treeimport java.util.*;class GFG { // Function to generate Fibonacci numbers // using Dynamic Programming static void printFibonacciLevel(int level) { // initialize previous and current values int prev1 = 0, prev2 = 1; int curr = 0; // left most index int left_index = (int) Math.pow(2, level - 1); for (int i = 1; i <= left_index; i++) { // compute curr if (i <= 2) { curr = i - 1; } else { curr = prev1 + prev2; // assigning values prev1 = prev2; prev2 = curr; } } // right most index int right_index = (int) Math.pow(2, level) - 2; for (int i = left_index; i <= right_index+1; i++) { System.out.print(curr + " "); // compute curr if (i <= 2) { curr = i - 1; } else { curr = prev1 + prev2; // assigning values prev1 = prev2; prev2 = curr; } } System.out.println(); } // Driver Code public static void main(String[] args) { int K = 4; // function call printFibonacciLevel(K); }} |
Python3
# Python3 program to print the Fibonacci numbers# present at K-th level of a Binary Treeimport math# Function to generate fibonacci numbers# using Dynamic Programmingdef printFibonacciLevel(level): # initialize previous and current values prev1 = 0 prev2 = 1 curr = 0 # left most index left_index = int(math.pow(2, level - 1)) for i in range(1, left_index + 1): # compute curr if i <= 2: curr = i - 1 else: curr = prev1 + prev2 # assigning values prev1 = prev2 prev2 = curr # right most index right_index = int(math.pow(2, level)) - 2 for i in range(left_index, right_index + 2): print(curr, end=" ") # compute curr if i <= 2: curr = i - 1 else: curr = prev1 + prev2 # assigning values prev1 = prev2 prev2 = curr print()# Driver Codeif __name__ == '__main__': K = 4 # function call printFibonacciLevel(K) |
C#
// C# program to print the Fibonacci numbers// present at K-th level of a Binary Treeusing System;class GFG { // Function to generate fibonacci numbers // using Dynamic Programming static void PrintFibonacciLevel(int level) { // initialize previous and current values int prev1 = 0, prev2 = 1; int curr = 0; // left most index int left_index = (int)Math.Pow(2, level - 1); for (int i = 1; i <= left_index; i++) { // compute curr if (i <= 2) { curr = i - 1; } else { curr = prev1 + prev2; // assigning values prev1 = prev2; prev2 = curr; } } // right most index int right_index = (int)Math.Pow(2, level) - 2; for (int i = left_index; i <= right_index + 1; i++) { Console.Write(curr + " "); // compute curr if (i <= 2) { curr = i - 1; } else { curr = prev1 + prev2; // assigning values prev1 = prev2; prev2 = curr; } } Console.WriteLine(); } // Driver Code static void Main(string[] args) { int K = 4; // function call PrintFibonacciLevel(K); }} |
Javascript
// JavaScript program to print the Fibonacci numbers// present at K-th level of a Binary Tree// Function to generate fibonacci numbers// using Dynamic Programmingfunction printFibonacciLevel(level) { // initialize previous and current values let prev1 = 0, prev2 = 1; let curr; // left most index let left_index = Math.pow(2, level - 1); for (let i = 1; i <= left_index; i++) { // compute curr if (i <= 2) { curr = i - 1; } else { curr = prev1 + prev2; // assigning values prev1 = prev2; prev2 = curr; } } // right most index let right_index = Math.pow(2, level) - 2; let ans = ""; for (let i = left_index; i <= right_index + 1; i++) { ans += curr; ans += " "; // compute curr if (i <= 2) { curr = i - 1; } else { curr = prev1 + prev2; // assigning values prev1 = prev2; prev2 = curr; } } console.log(ans);}// Driver Codelet K = 4;// function callprintFibonacciLevel(K); |
Output:
13 21 34 55 89 144 233 377
Time complexity: O(2^K) because we need to compute the Fibonacci numbers at each level of the binary tree up to level K
Auxiliary space : O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!