Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Tree Type’s
2.1.
For a given number of nodes, create a labelled binary tree.
3.
Code 
4.
Code
5.
Output
6.
Frequently asked questions
6.1.
What is the formula for calculating the number of binary trees with n nodes?
6.2.
How many different binary trees have four vertices?
6.3.
With N nodes, how many trees may be formed?
6.4.
With nine nodes, how many trees are possible?
6.5.
How many binary trees with three nodes have an ABC Postorder traversal?
7.
Conclusion
Last Updated: Mar 27, 2024

Enumeration of Binary Trees

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction 

The number of distinct binary trees formed from a given number of nodes of a binary tree, is known as the enumeration of a binary tree. The labelling of the binary tree's nodes can make a difference in how distinct these binary trees are. There are two forms of binary trees, depending on how the nodes in a binary tree are labelled:

Labelled trees

Tree Type’s

Labelled Binary Tree: In the Labelled Binary Tree, all of the nodes in a binary tree are given correct labels. In a labelled binary tree, this indicates that all of the nodes are organised in a specific order or sequence.
 

Unlabelled Binary Tree: The nodes in an unlabelled binary tree are not given labels. Because there is no unique attribute to distinguish the various nodes of a binary tree, the order or sequence of the nodes in the binary tree is irrelevant.

For a given number of nodes, create a labelled binary tree.

N = 2 (number of nodes)

 

Similarly, given N nodes, we may find the number of different labelled binary Trees.

N = 1
 count = 1


N = 2
 count = 4


N = 3
 count = 30


N = 4
 count = 336

 

We can see all of the types of arrangements made for unlabeled nodes for each of the labelled nodes here. As a result, the count will be n! * unlabeled binary tree count.

C(N) = n! * ( (2n!) / (n+1)! * n! ) )

There are two trees that are skewed to the left and two trees that are skewed to the right named as right-skewed trees and left-skewed trees.
 

1. Node 1 is the root node, and node 2 is the left child node in the first left-skewed tree. Node two operates as the root node of the left-skewed binary tree, with node one as the left child node in the second left-skewed tree.
 

2. Two right-skewed binary trees with the same number of nodes have the same number of nodes, but the positions of those nodes in the tree are different. Node one serves as the binary tree's root node, while node two serves as the tree's child node in the first right-skewed binary tree. In the second right-skewed binary tree, node two serves as the binary tree's root node, while node one serves as the tree's child node.

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

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 -

 

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.

Previous article
N-Ary Trees
Next article
Handshaking Lemma
Live masterclass