All Binary Trees

Easy
0/40
Average time to solve is 15m
10 upvotes
Asked in company
Flipkart

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
5
Sample Output 1:
0 0 0 0 0 -1 -1
0 0 0 -1 -1 0 0
Explanation for Sample Output 1:
For the first test case, the only two possible full binary trees are given below:

example example 

We can see that in each tree, the total number of nodes is five and each node either has 0 or 2 children. So both the trees are full binary trees. We can also observe that there is no other full binary tree containing five nodes.
Sample Input 2:
1
3
Sample Output 2:
0 0 0
Hint

Think of the number of nodes that the left and right subtrees can have.

Approaches (1)
Using Recursion

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:

  1. Create a hashmap, say memo that will, for every ā€˜Nā€™, store a vector containing roots of all possible trees having ā€˜Nā€™ nodes.
  2. 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.
  3. Now, create an empty vector, say allTrees, to store the roots of all possible trees.
  4. 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.
  5. 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.
  6. Now, store the result in memo by making memo[n]=allTrees.
  7. Return allTrees.
Time Complexity

O(2^N), where 'N' is the number of nodes required in all possible trees.

 

Every recursive call is making two branches: the first branch calling and returning the list for the left child of all valid full binary trees and the other branch doing the same for the right child. The depth of the recursion tree is the ā€˜Nā€™, as these recursive calls can go as deep as every number up to ā€˜Nā€™, in the worst case. So, the time complexity would be O(2 ^ N).

Space Complexity

O(2^N), where ā€˜Nā€™ is the number of nodes required in all possible trees.

 

Since for ā€˜2 ^ Nā€™ recursive calls, the recursion stack takes O(2 ^ N) space.

Code Solution
(100% EXP penalty)
All Binary Trees
Full screen
Console