1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Dynamic Programming Approach
2.1.
Steps of Algorithm
2.2.
Implementation in C++
2.3.
Implementation in Python
2.4.
Complexity analysis
3.
3.1.
What are the features of dynamic programming?
3.2.
What distinguishes dynamic programming from memoization and recursion?
3.3.
What are the benefits of a top-down approach?
4.
Conclusion
Last Updated: Mar 27, 2024

# Number of Binary Trees for given Preorder Sequence length

Shivani Singh
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

## Introduction

Here in this blog, we are asked to see various approaches to find the number of binary trees for a given preorder sequence length. We already are familiar with the concept of binary trees and graph traversals like preorder, postorder, and postorder. In preorder, we traverse the root node first, then the left node and right node. While in postorder, we traverse the left node first, then the right node, and in the last, we traverse the root node. And if we talk about inorder traversal, we traverse the left node first, then the root node, and in the end right node. So, let's see the approach in detail.

Source: binary tree

### Problem Statement

In this problem, we are given a preorder sequence length. And from that, we need to find the number of binary trees we can make. We can try different approaches to solve this problem. There are three traversal techniques available which are: preorder, postorder and inorder. Here we need to use preorder sequence length to get the desired result. Let us understand the problem statement with the help of an example.

Must Recommended Topic, Binary Tree Postorder Traversal.

### Sample Example

Let us understand this problem statement with the example given below.

From the above diagram, it is clear how we have to proceed with the problem statement. We got that how from the given sequence of preorder traversal we can calculate the number of binary trees. And what does the problem statement says? In the same way, we can create the number of binary trees possible for n = 5 and so on. Now let us see the approach to solve this problem.

## Dynamic Programming Approach

Dynamic programming is an optimization approach. We can use Dynamic Programming to optimize any recursive solution that has repeated calls for the same inputs. The idea is to simply save the results of subproblems so that we don't have to recalculate them later. This straightforward optimization reduces the time complexity from exponential to polynomial.

Source: dynamic programming

Let us see its algorithm to understand how dynamic programming is used here.

### Steps of Algorithm

Step 1: We will create an array to store the number of binary trees formed.

Step 2: Then we will initialize:

BinaryTree[i] = 0

BinaryTree[0] = BinaryTree[1] = 1

Step 3: We already are aware that for preorder 1 node there will be only one binary tree. So we will start the loop from n = 2, i.e. i=2 and the inner loop j will run from 0.

for (int i = 2 to i <= n and increment i)

for (int j = 0 to j < i and increment j)

BinaryTree[i] += BinaryTree[j] * BinaryTree[i - j - 1];

Step 4: Then for any value of n given, we will call the function and print the value of BinaryTree[n].

Let us see the implementation of this approach in the next section of this blog.

### Implementation in C++

``````#include <bits/stdc++.h>
using namespace std;
int CountBinaryTrees(int n)
{
int BinaryTree[n + 1];  //for storing number of Binary trees formed
memset(BinaryTree, 0, sizeof(BinaryTree));
BinaryTree[0] = BinaryTree[1] = 1;  //initializing that with 0 and 1 node there will be only one binary tree possible
for (int i = 2; i <= n; ++i)  //loop will start from 2, because we are already aware for 1 node
for (int j = 0; j < i; j++)
BinaryTree[i] += BinaryTree[j] * BinaryTree[i - j - 1];
return BinaryTree[n];
}
int main()
{
int n;
cout<<"enter the sequence of preorder: "<<endl;
cin>>n;
cout << "Total Possible Binary Trees for node "<< n << " are: "<<CountBinaryTrees(n) << endl;
return 0;
}``````

Output:

``````enter the sequence of preorder:
4
Total Possible Binary Trees for node 4 are: 14``````

### Implementation in Python

``````def CountBinaryTrees(n) :
BinaryTree = [0] * (n + 1)  #for storing count of binary trees
BinaryTree[0] = BinaryTree[1] = 1   #initializing for 0 and 1 there will be only 1 tree possible
for i in range(2, n + 1):  # we will start the loop from 2
for j in range(i):
BinaryTree[i] += BinaryTree[j] * BinaryTree[i - j - 1]
return BinaryTree[n]
if __name__ == '__main__':
n = int(input("Enter the sequence of preorder: "))
print("Total Possible Binary Trees for node ",n," are:",CountBinaryTrees(n))``````

Output:

``````Enter the sequence of preorder: 4
Total Possible Binary Trees for node  4  are: 14``````

Now let us analyze the time and complexity of the above approach.

### Complexity analysis

Time complexity

The time complexity of this algorithm is O(n^2) where n is the number of elements. The time complexity appears to be increased as a result of two loops that we are using in the code. The first loop i runs from 2 to i <= n and the second loop j runs from 0 to i. So overall it will take n^2 time. So the complexity will be O(n^2).

Space complexity

If we consider the space used to store the result then the space complexity is O(n) otherwise we can consider the space complexity to be O(1).

Check out this problem - Count Ways To Reach The Nth Stair

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

### What are the features of dynamic programming?

Optimal Substructures: A problem is said to have an optimal substructure property if the overall optimal solution is determined by evaluating the optimal solutions of all subproblems.

Overlapping subproblems: When a larger problem is divided into smaller problems, the smaller problems are referred to as subproblems.

### What distinguishes dynamic programming from memoization and recursion?

Recursion is the process of repeatedly calling the function itself. Memoization is a method of storing the solution to previously solved subproblems. Dynamic programming is a technique for solving recursions by storing the solutions to previously solved subproblems.

### What are the benefits of a top-down approach?

It is simple to comprehend and apply.

It only solves the subproblems when they are required.

It is simple to debug.

## Conclusion

To conclude this blog, firstly we discussed the problem statement and sample examples to understand the approach. For the first approach, we discussed its algorithm, implementations, and complexities.

Recommended problems -

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Live masterclass