Enumeration of Binary Trees

Code 

(will display the number of distinct unlabeled binary Trees).

#include <iostream>
using namespace std;

int fact(int n){
  if(n == 1)
      return 1;
  return n * fact(n - 1);
}

int distinctCountLabeledTree(int N){
  return ( (fact(N))*( fact(2*N) / ( fact(N+1)*fact(N)) ) ) ;
}

int main(){
  
  int N = 6;
  cout<<"There are”<<distinctCountLabeledTree(N)<<”distinct labelled Binary Trees.";
  return 0;
}

Code

(I will find the number of distinct unlabeled binary trees)

#include <iostream>
using namespace std;

int fact(int n){
  if(n == 1)
      return 1;
  return n * fact(n - 1);
}

int distinctCount(int N){
  return ( fact(2*N) / ( fact(N+1)*fact(N) ) );
}

int main(){
  
  int N = 7;
  cout<<"There are”<<distinctCount(N)<<”distinct unlabeled binary trees.”;
  return 0;
}

Output

There are 6 distinct unlabeled binary trees.

Must Recommended Topic, Binary Tree Postorder Traversal.

Frequently asked questions

What is the formula for calculating the number of binary trees with n nodes?

The total number of Binary Trees with n distinct keys (countBT(n)) = countBST(n) * n! Recommended: Please solve it on "PRACTICE" first, then proceed to the solution. The code below finds the count of BSTs and Binary Trees with n numbers. The code for finding the nth Catalan number is borrowed from this page.

How many different binary trees have four vertices?

It is used to count the number of binary trees. We can take things a step further by looking at binary trees with four vertices. The diagram above depicts all 14 potential binary trees with four vertices. However, there are only three structurally distinct versions. Trees 1, 2, 4, 5, 10, 11, 13, and 14 have a similar structure.

With N nodes, how many trees may be formed?

Suppose the nodes are comparable (unlabeled). In that case, the number of distinct binary trees equals the value above divided by the number of various permutations allowed for a binary tree structure, which is n! for a tree with n nodes.

With nine nodes, how many trees are possible?

As a result, consider the following approach: Count the number of binary trees having nine nodes. As you mentioned, this corresponds to the ninth Catalan number. C9 = 4862 is the answer.

How many binary trees with three nodes have an ABC Postorder traversal?

What is the number of binary trees with three nodes that provide sequences A, B, and C when explored in postorder? Because three is a tiny number, I quickly drew all conceivable binary trees and concluded that there could be five such binary trees for a given postorder.

Conclusion

This article has gone through Enumeration of Binary Trees and understands the types of trees and can find the tree by given nodes.

Want to learn more about the Data Structure in java? Click here.

Recommended problems -

• Vertical Order Traversal of a Binary Tree
• Leaf Nodes in Binary Tree
• Binary Array Sorting
• Shortest Common Supersequence

Take a look at how the Queue is implemented. It will make the concept more obvious.

Are you preparing to ace product-based company interviews with Amazon, Google, Microsoft, and others?

Please take a look at our course on operating systems.

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Ninja, have a great time learning.