Print all possible N-nodes Full Binary Trees

0 0 12 minutes read

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:
1. Create a List, say list containing the class nodes.
2. If N =1, then add nodes(0, NULL, NULL) in the list.
3. 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.
    1. Recursively call the function allPossibleBFT with y as the parameter inside the above call and assign it to the node right.
    2. Now create a new Node with parameters as (0, NULL, NULL).
    3. Assign Node.left as left and Node.right as right.
    4. Add Node to the List.
4. 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>

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]

Time Complexity: O(2^N)
Space Complexity: O(2^N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!