Introduction
 
Let us learn about the fundamentals of Dynamic Programming before solving the questions on it. We will understand the basics of Dynamic numbers using a simple problem of Fibonacci numbers. 
 

Fibonacci Numbers 
 

Fibonacci numbers are a sequence in which each term is the sum of the two preceding terms. It starts with Term 0 = 0 and Term 1 = 1 and continues as 0, 1, 1, 2, 3, and so on. 
 

Recursive Approach 
 

Now, the challenge is to find the Nth Fibonacci number. Can this be accomplished through recursion? Indeed, it can. 

To compute the Nth Fibonacci number using recursion, we realize that it relies on the values of N-1 and N-2. If we can find these values, their sum will give us the Nth Fibonacci number. The base case for this recursive approach is the values of Term0 and Term1.
 

<figure><img src="https://lh4.googleusercontent.com/GzcAf9iUdqIu7XHNOCJ8Ozl5U3lKx6GFNpTNx2uYlwgz7BtY6TRJSesMTrD7wUxeyubDH2emrP9awBlNhgn_tRSSdp-kYg6zCoLLTAMW_ERJ1Y5iAcYnoY_4_HVcKWh4p8oAYKcH0dEoCytY72nYxT0" alt="" height="" width=""/> 
 
</figure>
 
 
Time Complexity Analysis 
 

One critical question to answer is the time complexity of this recursive approach. Is it O(N) or greater than O(N)? 

To understand this, let's create a recursion tree diagram. Suppose we want to find the 5th Fibonacci number, f(5). It will trigger f(4) and f(3), the process continues. 
 

<figure><img src="https://imgtr.ee/images/2023/09/21/2568542feb30c82c3791bdfc9cfcd81f.png" height="auto" width="700px" alt=""/></figure>
 
 
 
However, there's a noticeable issue: redundancy. 
 
 
Overlapping Sub-Problems 
 

As the recursion unfolds, you'll find that you're recomputing values multiple times. For instance, f(3) is calculated both at time T=T' and T=T''. This redundancy occurs due to overlapping sub-problems – a common characteristic of recursive algorithms. &nbsp; 
 
 

<figure><img src="https://imgtr.ee/images/2023/09/21/f69e626123b3a540e46a256f6cc4e43f.png" height="auto" width="700px" alt=""/></figure>
 
 
 
Dynamic Programming Solution 
 

To address this inefficiency, we turn to dynamic programming. Instead of recomputing values, we store them once calculated, eliminating the repetition of work. 
 

Let us understand this with the help of a Binary Tree Analogy 
 

The recursion tree for this problem resembles a binary tree. What's its height? It's N. This height represents the longest root-to-leaf path. With a height of N, the number of nodes in this binary tree is 2^N. 
 

Time Complexity 
 

While adding two numbers has a time complexity of O(1), the sheer number of function calls in this binary tree leads to a time complexity of 2^N. This complexity can be extremely demanding for large values of N, such as calculating the 100th Fibonacci number. 
 

In conclusion, the straightforward recursive approach to finding the sum of Fibonacci numbers has a time complexity of 2^N due to overlapping sub-problems. Dynamic programming provides a more efficient solution by storing previously computed values, making it possible to calculate Fibonacci numbers for larger values of N without overwhelming computational demands. 
 
 
&nbsp;

Dynamic Programming: The Foundation of Efficient Problem Solving

Introduction
 
Let us learn the difference between solving questions iteratively and recursively.&nbsp;
We will understand this with the sum of the first N natural numbers. In this discussion, we examine the task of calculating the sum of the first N natural numbers. This problem can be approached in two ways: iteratively and recursively. Each approach has its merits, and we'll delve into the reasoning behind them. 
 

Iterative Approach 
 

The Problem: 
 
When tasked with calculating the sum of natural numbers up to a given N, one straightforward approach is to start from 1 and progressively add each subsequent number until reaching N. For instance: 

Sum of the first 1 natural number = 1
Sum of the first 2 natural numbers = 1 + 2 = 3
Sum of the first 3 natural numbers = 1 + 2 + 3 = 6 
 

Analyzing the Iterative Approach 

However, this method raises a question: Is it intelligent to repeatedly start from 1 and add up to N? Not at all. Consider that the sum of N natural numbers always overlaps with the sum of N-1 natural numbers. This inefficiency can be resolved through a better approach. 
 

For example, you need to find the sum of 4 natural numbers. A basic approach to do this: 
Sum of the first 1 natural number = 1
Sum of the first 2 natural numbers = 1 + 2 = 3
Sum of the first 3 natural numbers = 1 + 2 + 3 = 6 
Sum of the first 4 natural numbers = 1 + 2 + 3 + 4= 10 
 
If you look carefully, you can store the sum of the first two natural numbers and then find the sum of the first three natural numbers using the stored value. Similarly, we can store the value of the sum of the first 3 natural numbers and find the sum of the first 4 natural numbers by just adding 4 to the stored value. 
 
 The idea here is to recognize that the sum from 1 to N is related to the sum from 1 to N-1 by the equation: 

Sum(N) = Sum(N-1) + N
 

<figure><img src="https://lh4.googleusercontent.com/WYus3otC60Oh4o6INBPpnnlWkJQTu4Bo5Q94ThNfsfG63VZKoYi5byZKOECV5L-eVJEXCtenYXYZ3Awx3c8rry3XSb8zouSEpkwA_O2nGZ__v8o0GqOdZxEf3HuT2AuCYm_Wc8uGYiMK0baTQEXotF4" alt="" height="" width=""/>&nbsp; 
 
</figure>
 
Recursive Approach: 
 

In recursion, every equation has a base case, and in this scenario, the base case is N = 1. This is crucial because when N equals 1, the calculation extends to N = 0, which is undefined within the context of natural numbers. 

To address this problem wisely, we can implement a recursive approach. Here's how it works:
 
Now, if we solve this question recursively, the problem says to print the sum of the first N natural numbers. If your N=3, print 6. So how can you write this code? Can you write a recursive code which when given a number N prints me an integer and that integer is the sum of N natural numbers? 
 

Start with calling func(N) which delegates work to func(N-1) and adds N to its result. 
 

<figure><img src="https://lh4.googleusercontent.com/x5Y8uWYnqf0lHK1oRpZ3XHRzbKnv5NVGJI5uQ2vQgxhU1GTKCIf4DCsbtY9vd1eAuRs1mMCE8F3yJkEaGt_nMSqrCC0AJIf4ltw0o5AZNUjTJofa0jAMc0uFhKZ6TNyPUl-cLQgcskdyCJ2xSgKPuqM" alt="" height="" width=""/> 
</figure>
 
This recursive approach still maintains a time complexity of O(N) due to ~N function calls, each doing unit work.
 
The iterative approach means the bottom-top approach because N is not directly attacked here. It crawls its way from 1 to N so it is a bottom-top approach. 
 
The second approach is a top-bottom approach because it directly attacks N. It first attempts to find the sum of N, and for that, it realizes that it has to find the sum of N-1, N-2 so on till the sum of 1. 
 

Conclusion 
 

In summary, when tasked with finding the sum of the first N natural numbers, you have the choice between an iterative bottom-up approach and a recursive top-down approach. Each approach has its own strengths and weaknesses, and the choice depends on the specific requirements of your problem. Understanding these approaches can help you tackle similar problems more effectively. 
&nbsp;

Understanding Recurrence Relations: Bottom-Top Approach & Top-Bottom Approach Explained

We have covered the <a href="https://blogs.programmingpathshala.com/tree-data-structure/86">basics of Tree</a> and <a href="https://blogs.programmingpathshala.com/binary-tree/87">Binary Tree</a>. Now we will learn tree levels and height by breaking down complex ideas into simple terms, helping you grasp the main concepts and their importance.
 
Simplifying Tree Levels and Height
 
To make sense of tree levels and height, let's start by looking at the number of nodes and edges in a binary tree. A tree with N nodes is linked by N-1 edges. Even a single node matters because it can create new edges.
 
Following Paths: Navigating the Binary World
 
Imagine you're in a binary tree and need to move from one node to another.
Let us say in the below given tree you have to go from 9 to 1. Can you find the number of paths that are there to do so?
 
 
<figure><img src="https://imgtr.ee/images/2023/09/01/52ae8fc2b56d962b7632fd21ae85ab4f.png" height="auto" width="700px" alt=""/></figure>
 
 
 
The answer is one. There is only one way to traverse from 9 to 1. In a binary tree, you will always find only one path to traverse from any node to another node. However, there is more than one path to traverse only when there is a cyclic pattern in a tree.&nbsp;
 
The Perfect Tree: Balanced Beauty
 
 
<figure><img src="https://imgtr.ee/images/2023/09/01/f134af8c1ff32cc8411de31bc2bf84c9.png" height="auto" width="700px" alt=""/></figure>
 
 
Perfectly Balanced Tree – a tree with full levels and balanced branches. How do the levels of this tree connect to its height? Let's reveal the patterns hidden within binary trees. There are 4 levels in this tree. The number of levels plus one is called the height of the tree. Have a look below:&nbsp;
 
 
 
<figure><img src="https://imgtr.ee/images/2023/09/01/d6c49ec64310a3e8d3fa43204d5c81b3.png" height="auto" width="700px" alt=""/></figure>
 
 
 
 
Now, can you tell the number of nodes this tree has?&nbsp;
 
If you carefully observe the number of nodes in each level is increasing exponentially. Get a clear understanding below:
 
<figure><img src="https://imgtr.ee/images/2023/09/01/d240977927344377bcd1da6c393b640a.png" height="auto" width="700px" alt=""/></figure>
 
 
Here we can identify that this is a G.P. series. Now with the help of this we can calculate the number of nodes.&nbsp;
 

<figure><img src="https://imgtr.ee/images/2023/09/01/0bb2d0d7e72fa6101cd4b5978669adbf.png" height="auto" width="700px" alt=""/></figure>
 

Now you should move forward to solve a question &nbsp;to write a program to <a href="https://youtu.be/DW98-8bbQoE?si=tINrkB0NyFoEBwcp">compute the maximum depth/height of a binary tree. </a> 
 &nbsp;&nbsp;&nbsp;

Blogs

Understanding Tree Levels and Height in Binary Trees

Dynamic Programming: The Foundation of Efficient Problem Solving

Understanding Recurrence Relations: Bottom-Top Approach & Top-Bottom Approach Explained

Understanding Tree Levels and Height in Binary Trees

Dynamic Programming: The Foundation of Efficient Problem Solving

Understanding Recurrence Relations: Bottom-Top Approach & Top-Bottom Approach Explained

Understanding Tree Levels and Height in Binary Trees

Data Structures & Algorithms

Interview Preparation

Competitive Programming

Student Experiences

About Us

Time and Space Complexity

Want to know more
about our courses?

Blogs

Dynamic Programming: The Foundation of Efficient Problem Solving

Data Structures & Algorithms

Interview Preparation

Competitive Programming

Student Experiences

About Us

Time and Space Complexity

Want to know more about our courses?

Want to know more
about our courses?