Last Updated: 27 Mar, 2021

All Binary Trees

Easy

Asked in company

Solve now

Problem statement

You are given a single integer ‘N’. Your task is to print all possible full binary trees containing ‘N’ nodes. Each node must have 0 as its value.

Note:

A full binary tree is a binary tree where every node has exactly 0 or 2 children.

Input Format:

The first and only line contains a single integer ‘N’, denoting the number of nodes required in each tree.

Output Format:

For each test case, print in a separate line all the nodes of the tree. Trees can be printed in any order but all the nodes of a tree must be printed in level order. If a node does not exist, '-1' should be printed in its place. All the trees must be printed in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N < 20

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach:

The approach is to divide the problem into smaller subproblems. We can observe that if there are ‘N’ nodes and the left subtree have ‘X’ nodes then the right subtree will have ‘N-1-X’ nodes. So for all possible values of ‘X’, we can get trees having ‘X’ nodes in the left subtree and ‘N-1-X’ nodes in the right subtree and thus we can combine these and we can get all trees that contain ‘N’ nodes. We can also observe that if ‘N’ is even, we can not have any full binary tree.

Steps:

Create a hashmap, say memo that will, for every ‘N’, store a vector containing roots of all possible trees having ‘N’ nodes.
If the memo has a vector for ‘N’, it means that we have already calculated the result for this ‘N’ and we can simply return that vector.
Now, create an empty vector, say allTrees, to store the roots of all possible trees.
If ‘N’ is 1, then only one tree is possible. This tree contains only one node having a value of 0. Push this tree in allTrees.
Now, if ‘N’ is odd, do:
1. For all leftNodes_count=0 to leftNodes_count=n,
  1. Define rightNodes_count = n-1-leftNodes_count.
  2. For all leftSubTree in findAllTrees(leftNodes_count) and for all rightSubTree in findAllTrees(rightNodes_count), do:
    1. Create a new tree having a single node with a value = 0.
    2. Make leftSubTree as the left subtree of this newly created tree.
    3. Make rightSubTree as the right subtree of this newly created tree.
    4. Push this tree in allTrees.
Now, store the result in memo by making memo[n]=allTrees.
Return allTrees.

Solve now