Print all possible N-nodes Full Binary Trees
Given an integer N, the task is to print all possible Full Binary Trees with N nodes. The value at the nodes does not contribute to be a criteria for different Full Binary Tree, except for NULL,so take them as 0.
A full binary tree is a binary tree in which every node has exactly 0 or 2 children.
Examples:
Input: N = 7
Output: [[0, 0, 0, null, null, 0, 0, null, null, 0, 0, null, null, null, null],
[0, 0, 0, null, null, 0, 0, 0, 0, null, null, null, null, null, null],
[0, 0, 0, 0, 0, null, null, null, null, 0, 0, null, null, null, null],
[0, 0, 0, 0, 0, null, null, 0, 0, null, null, null, null, null, null],
[0, 0, 0, 0, 0, 0, 0, null, null, null, null, null, null, null, null]]
Explanation: The possible full binary trees are –
0 | 0 | 0 | 0 | 0
/ \ | / \ | / \ | / \ | / \
0 0 | 0 0 | 0 0 | 0 0 | 0 0
/ \ | / \ | / \ | / \ | / \ / \
0 0 | 0 0 | 0 0 | 0 0 | 0 0 0 0
/ \ | / \ | / \ | / \ |
0 0 | 0 0 | 0 0 | 0 0 |Input: N = 5
Output: [[0, 0, 0, null, null, 0, 0, null, null, null, null],
[0, 0, 0, 0, 0, null, null, null, null, null, null]]Input: N = 9
Output: [[0,0,0,null,null,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,null,null,0,0,0,0],[0,0,0,null,null,0,0,0,0,0,0],[0,0,0,null,null,0,0,0,0,null,null,null,null,0,0],[0,0,0,null,null,0,0,0,0,null,null,0,0],[0,0,0,0,0,0,0,null,null,null,null,null,null,0,0],[0,0,0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,0,0,null,null,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0,null,null,0,0],[0,0,0,0,0,null,null,null,null,0,0,0,0],[0,0,0,0,0,null,null,0,0,0,0],[0,0,0,0,0,null,null,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0,null,null,0,0]]
Approach: The simplest way to solve the problem is to use recursion using the concept of memoization and check for each subtree if there is a odd number of nodes or not because a full binary tree has odd nodes. Follow the steps below to solve the problem:
- Initialize a hashMap, say hm that stores all the Full Binary Tree.
- Create a function, say allPossibleBFT with the parameter as N by performing the following steps:
- Create a List, say list containing the class nodes.
- If N =1, then add nodes(0, NULL, NULL) in the list.
- Now check if N is odd, then Iterate in the range [0, N-1] using the variable x and perform the following steps:
- Initialize a variable, say y as N – 1 – x.
- Recursively call the function allPossibleBFT with x as the parameter and assign it to the node left.
- Recursively call the function allPossibleBFT with y as the parameter inside the above call and assign it to the node right.
- Now create a new Node with parameters as (0, NULL, NULL).
- Assign Node.left as left and Node.right as right.
- Add Node to the List.
- After performing the above steps, insert list in the hashMap hm.
- After performing all the steps, print the Full Binary Trees that are in the list.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Class for creating node and // its left and right child struct Node { Node* left; Node* right; int data; Node( int data, Node* left, Node* right) { this ->data = data; this ->left = left; this ->right = right; } }; // Function to traverse the tree and add all // the left and right child in the list al void display(Node* node, vector< int > &al) { // If node = null then terminate the function if (node == nullptr) { return ; } // If there is left child of Node node // then insert it into the list al if (node->left != nullptr) { al.push_back(node->left->data); } // Otherwise insert null in the list else { al.push_back(INT_MIN); } // Similarly, if there is right child // of Node node then insert it into // the list al if (node->right != nullptr) { al.push_back(node->right->data); } // Otherwise insert null else { al.push_back(INT_MIN); } // Recursively call the function // for left child and right child // of the Node node display(node->left, al); display(node->right, al); } // Save tree for all n before recursion. map< int , vector<Node*>> hm; vector<Node*> allPossibleFBT( int n) { // Check whether tree exists for given n value or not. if (hm.find(n) == hm.end()) { // Create a list containing nodes vector<Node*> list; // If N=1, Only one tree can exist // i.e. tree with root. if (n == 1) { list.push_back( new Node(0, nullptr, nullptr)); } // Check if N is odd because binary full // tree has N nodes else if (n % 2 == 1) { // Iterate through all the nodes that // can be in the left subtree for ( int x = 0; x < n; x++) { // Remaining Nodes belongs to the // right subtree of the node int y = n - 1 - x; // Iterate through all left Full Binary Tree // by recursively calling the function vector<Node*> xallPossibleFBT = allPossibleFBT(x); vector<Node*> yallPossibleFBT = allPossibleFBT(y); for ( int Left = 0; Left < xallPossibleFBT.size(); Left++) { // Iterate through all the right Full // Binary tree by recursively calling // the function for ( int Right = 0; Right < yallPossibleFBT.size(); Right++) { // Create a new node Node* node = new Node(0, nullptr, nullptr); // Modify the left node node->left = xallPossibleFBT[Left]; // Modify the right node node->right = yallPossibleFBT[Right]; // Add the node in the list list.push_back(node); } } } } //Insert tree in Dictionary. hm.insert({n, list}); } return hm[n]; } int main() { // You can take n as input from user // Here we take n as 7 for example purpose int n = 7; // Function Call vector<Node*> list = allPossibleFBT(n); // Print all possible binary full trees for ( int root = 0; root < list.size(); root++) { vector< int > al; al.push_back((list[root])->data); display(list[root], al); cout << "[" ; for ( int i = 0; i < al.size(); i++) { if (i != al.size() - 1) { if (al[i]==INT_MIN) cout << "null, " ; else cout << al[i] << ", " ; } else { if (al[i]==INT_MIN) cout << "null]" ; else cout << al[i] << "]" ; } } cout << endl; } return 0; } // This code is contributed by decode2207. |
Java
// JAVA program for the above approach import java.util.*; import java.io.*; class GFG { // Class for creating node and // its left and right child public static class Node { int data; Node left; Node right; Node( int data, Node left, Node right) { this .data = data; this .left = left; this .right = right; } } // Function to traverse the tree and add all // the left and right child in the list al public static void display(Node node, List<Integer> al) { // If node = null then terminate the function if (node == null ) { return ; } // If there is left child of Node node // then insert it into the list al if (node.left != null ) { al.add(node.left.data); } // Otherwise insert null in the list else { al.add( null ); } // Similarly, if there is right child // of Node node then insert it into // the list al if (node.right != null ) { al.add(node.right.data); } // Otherwise insert null else { al.add( null ); } // Recursively call the function // for left child and right child // of the Node node display(node.left, al); display(node.right, al); } // Driver Code public static void main(String[] args) { // Given Input int n = 7 ; // Function Call List<Node> list = allPossibleFBT(n); // Print all possible binary full trees for (Node root: list) { List<Integer> al = new ArrayList<>(); al.add(root.data); display(root, al); System.out.println(al); } } // Save tree for all n before recursion. static HashMap<Integer, List<Node> > hm = new HashMap<>(); public static List<Node> allPossibleFBT( int n) { // Check whether tree exists for given n value or not. if (!hm.containsKey(n)) { // Create a list containing nodes List<Node> list = new LinkedList<>(); // If N=1, Only one tree can exist // i.e. tree with root. if (n == 1 ) { list.add( new Node( 0 , null , null )); } // Check if N is odd because binary full // tree has N nodes else if (n % 2 == 1 ) { // Iterate through all the nodes that // can be in the left subtree for ( int x = 0 ; x < n; x++) { // Remaining Nodes belongs to the // right subtree of the node int y = n - 1 - x; // Iterate through all left Full Binary Tree // by recursively calling the function for (Node left: allPossibleFBT(x)) { // Iterate through all the right Full // Binary tree by recursively calling // the function for (Node right: allPossibleFBT(y)) { // Create a new node Node node = new Node( 0 , null , null ); // Modify the left node node.left = left; // Modify the right node node.right = right; // Add the node in the list list.add(node); } } } } //Insert tree in HashMap. hm.put(n, list); } return hm.get(n); } } |
Python3
# Python3 program for the above approach import sys # Class for creating node and # its left and right child class Node: def __init__( self , data, left, right): self .data = data self .left = left self .right = right # Function to traverse the tree and add all # the left and right child in the list al def display(node, al): # If node = null then terminate the function if (node = = None ): return # If there is left child of Node node # then insert it into the list al if (node.left ! = None ): al.append(node.left.data) # Otherwise insert null in the list else : al.append( - sys.maxsize) # Similarly, if there is right child # of Node node then insert it into # the list al if (node.right ! = None ): al.append(node.right.data) # Otherwise insert null else : al.append( - sys.maxsize) # Recursively call the function # for left child and right child # of the Node node display(node.left, al) display(node.right, al) # Save tree for all n before recursion. hm = {} def allPossibleFBT(n): # Check whether tree exists for given n value or not. if n not in hm: # Create a list containing nodes List = [] # If N=1, Only one tree can exist # i.e. tree with root. if (n = = 1 ): List .append(Node( 0 , None , None )) # Check if N is odd because binary full # tree has N nodes elif (n % 2 = = 1 ): # Iterate through all the nodes that # can be in the left subtree for x in range (n): # Remaining Nodes belongs to the # right subtree of the node y = n - 1 - x # Iterate through all left Full Binary Tree # by recursively calling the function xallPossibleFBT = allPossibleFBT(x) yallPossibleFBT = allPossibleFBT(y) for Left in range ( len (xallPossibleFBT)): # Iterate through all the right Full # Binary tree by recursively calling # the function for Right in range ( len (yallPossibleFBT)): # Create a new node node = Node( 0 , None , None ) # Modify the left node node.left = xallPossibleFBT[Left] # Modify the right node node.right = yallPossibleFBT[Right] # Add the node in the list List .append(node) #Insert tree in Dictionary. hm[n] = List return hm[n] # Given Input n = 7 # Function Call List = allPossibleFBT(n) # Print all possible binary full trees for root in range ( len ( List )): al = [] al.append( List [root].data) display( List [root], al) print ( "[" , end = "") for i in range ( len (al)): if (i ! = len (al) - 1 ): if (al[i] = = - sys.maxsize): print ( "null, " , end = "") else : print (al[i], end = ", " ) else : if (al[i] = = - sys.maxsize): print ( "null]" , end = "") else : print (al[i], end = "]" ) print () # This code is contributed by mukesh07. |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Class for creating node and // its left and right child public class Node { public int data; public Node left; public Node right; public Node( int data, Node left, Node right) { this .data = data; this .left = left; this .right = right; } } // Function to traverse the tree and add all // the left and right child in the list al public static void display(Node node, List< int > al) { // If node = null then terminate the function if (node == null ) { return ; } // If there is left child of Node node // then insert it into the list al if (node.left != null ) { al.Add(node.left.data); } // Otherwise insert null in the list else { al.Add( int .MinValue); } // Similarly, if there is right child // of Node node then insert it into // the list al if (node.right != null ) { al.Add(node.right.data); } // Otherwise insert null else { al.Add( int .MinValue); } // Recursively call the function // for left child and right child // of the Node node display(node.left, al); display(node.right, al); } // Driver Code public static void Main(String[] args) { // Given Input int n = 7; // Function Call List<Node> list = allPossibleFBT(n); // Print all possible binary full trees foreach (Node root in list) { List< int > al = new List< int >(); al.Add(root.data); display(root, al); foreach ( int i in al){ if (i== int .MinValue) Console.Write( "null, " ); else Console.Write(i+ ", " ); } Console.WriteLine(); } } // Save tree for all n before recursion. static Dictionary< int , List<Node> > hm = new Dictionary< int , List<Node> >(); public static List<Node> allPossibleFBT( int n) { // Check whether tree exists for given n value or not. if (!hm.ContainsKey(n)) { // Create a list containing nodes List<Node> list = new List<Node>(); // If N=1, Only one tree can exist // i.e. tree with root. if (n == 1) { list.Add( new Node(0, null , null )); } // Check if N is odd because binary full // tree has N nodes else if (n % 2 == 1) { // Iterate through all the nodes that // can be in the left subtree for ( int x = 0; x < n; x++) { // Remaining Nodes belongs to the // right subtree of the node int y = n - 1 - x; // Iterate through all left Full Binary Tree // by recursively calling the function foreach (Node left in allPossibleFBT(x)) { // Iterate through all the right Full // Binary tree by recursively calling // the function foreach (Node right in allPossibleFBT(y)) { // Create a new node Node node = new Node(0, null , null ); // Modify the left node node.left = left; // Modify the right node node.right = right; // Add the node in the list list.Add(node); } } } } //Insert tree in Dictionary. hm.Add(n, list); } return hm[n]; } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program for the above approach // Class for creating node and // its left and right child class Node { constructor(data, left, right) { this .left = left; this .right = right; this .data = data; } } // Function to traverse the tree and add all // the left and right child in the list al function display(node, al) { // If node = null then terminate the function if (node == null ) { return ; } // If there is left child of Node node // then insert it into the list al if (node.left != null ) { al.push(node.left.data); } // Otherwise insert null in the list else { al.push(Number.MIN_VALUE); } // Similarly, if there is right child // of Node node then insert it into // the list al if (node.right != null ) { al.push(node.right.data); } // Otherwise insert null else { al.push(Number.MIN_VALUE); } // Recursively call the function // for left child and right child // of the Node node display(node.left, al); display(node.right, al); } // Save tree for all n before recursion. let hm = new Map(); function allPossibleFBT(n) { // Check whether tree exists for given n value or not. if (!hm.has(n)) { // Create a list containing nodes let list = []; // If N=1, Only one tree can exist // i.e. tree with root. if (n == 1) { list.push( new Node(0, null , null )); } // Check if N is odd because binary full // tree has N nodes else if (n % 2 == 1) { // Iterate through all the nodes that // can be in the left subtree for (let x = 0; x < n; x++) { // Remaining Nodes belongs to the // right subtree of the node let y = n - 1 - x; // Iterate through all left Full Binary Tree // by recursively calling the function let xallPossibleFBT = allPossibleFBT(x); let yallPossibleFBT = allPossibleFBT(y); for (let Left = 0; Left < xallPossibleFBT.length; Left++) { // Iterate through all the right Full // Binary tree by recursively calling // the function for (let Right = 0; Right < yallPossibleFBT.length; Right++) { // Create a new node let node = new Node(0, null , null ); // Modify the left node node.left = xallPossibleFBT[Left]; // Modify the right node node.right = yallPossibleFBT[Right]; // Add the node in the list list.push(node); } } } } //Insert tree in Dictionary. hm.set(n, list); } return hm.get(n); } // Given Input let n = 7; // Function Call let list = allPossibleFBT(n); // Print all possible binary full trees for (let root = 0; root < list.length; root++) { let al = []; al.push(list[root].data); display(list[root], al); document.write( "[" ); for (let i = 0; i < al.length; i++){ if (i != al.length - 1) { if (al[i]==Number.MIN_VALUE) document.write( "null, " ); else document.write(al[i]+ ", " ); } else { if (al[i]==Number.MIN_VALUE) document.write( "null]" ); else document.write(al[i]+ "]" ); } } document.write( "</br>" ); } // This code is contributed by divyeshrabadiya07. </script> |
[0, 0, 0, null, null, 0, 0, null, null, 0, 0, null, null, null, null] [0, 0, 0, null, null, 0, 0, 0, 0, null, null, null, null, null, null] [0, 0, 0, 0, 0, null, null, null, null, 0, 0, null, null, null, null] [0, 0, 0, 0, 0, null, null, 0, 0, null, null, null, null, null, null] [0, 0, 0, 0, 0, 0, 0, null, null, null, null, null, null, null, null]
Time Complexity: O(2N)
Space Complexity: O(2N)