Unique Binary Search Trees II

Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

Example:

Input: n= 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

Approach

Java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class UniqueBinarySearchTreesII {
    public static void main(String[] args) {

        int n = 3;
        int i = 0;
        List<TreeNode> trees = generateTrees(n);
        System.out.print("[");
        for (TreeNode treeNode : trees) {
            System.out.print("[");
            printTree(treeNode);
            i++;
            if (trees.size() == i)
                System.out.print("]");
            else
                System.out.print("],");

        }
        System.out.print("]");
    }

    // function to generate all trees whose
    // values lies between start and end
    static List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> res = new ArrayList<TreeNode>();

        // base case
        if (start > end) {
            res.add(null);
            return res;
        }

        // itearte from start till end
        for (int i = start; i <= end; i++) {

            // generate left subtree
            List<TreeNode> left = generateTrees(start, i - 1);

            // generate right subtree
            List<TreeNode> right = generateTrees(i + 1, end);

            // make the tree
            for (int j = 0; j < left.size(); j++) {
                TreeNode left1 = left.get(j);
                for (int k = 0; k < right.size(); k++) {
                    TreeNode right1 = right.get(k);
                    TreeNode node = new TreeNode(i);
                    node.left = left1;
                    node.right = right1;
                    res.add(node);
                }
            }
        }
        return res;
    }

    static List<TreeNode> generateTrees(int n) {
        List<TreeNode> res = new ArrayList<TreeNode>();
        if (n == 0)
            return res;
        return generateTrees(1, n);
    }

    static void printTree(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        List<String> vec = new ArrayList<String>();
        while (!q.isEmpty()) {
            root = q.poll();
            if (root == null)
                vec.add("null");
            else
                vec.add(String.valueOf(root.val));
            if (root != null) {
                q.add(root.left);
                q.add(root.right);
            }
        }
        int j = vec.size() - 1;
        for (int i = 0; i < j; i++)
            System.out.print(vec.get(i) + ",");
        System.out.print(vec.get(j));
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
};

//function to generate all trees whose
//values lies between start and end
vector<TreeNode*> generateTrees(int start,int end)
{
        vector<TreeNode*> res;

        //base case
        if(start>end)
        {
            res.push_back(NULL);
            return res;
        }

        //itearte from start till end
       for(int i=start;i<=end;i++)
       {

           //generate left subtree
           vector<TreeNode*> left=generateTrees(start,i-1);

           //generate right subtree
           vector<TreeNode*> right=generateTrees(i+1,end);

           //make the tree
           for(int j=0;j<left.size();j++)
           {
               TreeNode *left1=left[j];
               for(int k=0;k<right.size();k++)
               {
                   TreeNode *right1=right[k];
                   TreeNode *node=new TreeNode(i);
                   node->left=left1;
                   node->right=right1;
                   res.push_back(node);
               }
           }
       }
        return res;
}
vector<TreeNode*> generateTrees(int n) 
{
        vector<TreeNode*> res;
        if(n==0)
               return res;
      return generateTrees(1,n);   
}
void printTree(TreeNode *root)
{
    queue<TreeNode*>q;
    q.push(root);
    vector<string> vec;
    while(!q.empty())
     {
         root=q.front();
         q.pop();
         if(root==NULL)
            vec.push_back("null");
         else
            vec.push_back(to_string(root->data));
        if(root!=NULL)
          {
              q.push(root->left);
              q.push(root->right);
          }
     }
     int j=vec.size()-1;
     while(j>0&&vec[j]=="null")
        j--;
      vec.resize(j);
      for(int i=0;i<j;i++)
        cout<<vec[i]<<",";
      cout<<vec[j];
}

int main()
{
    int n=3;
    vector<TreeNode*> trees=generateTrees(n);
    cout<<"[";
    for(int i=0;i<trees.size();i++)
       {
           cout<<"[";
           printTree(trees[i]);
           cout<<"]";
           if(i!=trees.size()-1)
             cout<<",";
       }
      cout<<"]";
    return 0;
}