Table of contents
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.
Frequently Asked Questions
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

Author Shivani Singh
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

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;
}
You can also try this code with Online C++ Compiler
Run Code

 

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))
You can also try this code with Online Python Compiler
Run Code

 

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 

Frequently Asked Questions

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