What is the Memory Limit?


My solution won’t pass because of memory limit. I don’t understand what am I supposed to do. I stored the trees, then deleted duplicate trees. I also cleared all my containers after using them. Will it only pass if I never created duplicate trees to begin with?


Probably duplicate trees are the problem, if it’s not then try clearing all the memory you used (which in c++ if you used a vector v would be something like v.clear()). Anyways, you should try coming up with a solution without duplicates.


I do not have duplicate trees in my solution and I am using dynamic programming, yet I can only successfully solve up to N=11. With N=12 I get a Memory limit exceeded. I am using python3. I wonder if the memory limits are set too strict for this problem.


problem stupid, memory limits way too strict.


Don’t create the same trees over and over. Store the already created trees’ root node in a (arraylist) cache and when trying to generate a tree already generated, just re-use the already created tree.



I don’t create duplicate trees, and still have MLE problem. Apparently the configuration of the problem is wrong.

Here’s the code if you need to verify.

 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };

struct storeItem {
    storeItem(int parent, int current, int start, int end)
        : parent(parent), current(current), start(start), end(end) {}
    int parent;
    int current;
    int start;
    int end;

vector<storeItem> store;
int size;

vector<TreeNode*> output;

void doOutput() {
    vector<int> parent(size + 1);
    for (const storeItem& item : store) {
        if (item.current == -1)
        // The following will be done multiple times due to the construction of store,
        // but it's okay.
        parent[item.current] = item.parent;

    vector<TreeNode*> nodes(size + 1);
    for (int i = 1; i <= size; ++i)
        nodes[i] = new TreeNode(i);

    for (int i = 1; i <= size; ++i) {
        if (parent[i] == -1)
        else if (i < parent[i])
            nodes[parent[i]]->left = nodes[i];
            nodes[parent[i]]->right = nodes[i];

int num_output = 0;

void generate(int to_process) {
    if (to_process == store.size()) {
    int current = store[to_process].current;
    int start = store[to_process].start;
    int end = store[to_process].end;
    if (end < start) {
        generate(to_process + 1);
    for (int mid = start; mid <= end; ++mid) {
        store.emplace_back(current, mid, start, mid - 1);
        store.emplace_back(current, mid, mid + 1, end);
        generate(to_process + 1);

vector<TreeNode*> Solution::generateTrees(int A) {
    size = A;
    store.emplace_back(-1, -1, 1, A);


    return std::move(output);


Finally I tried the insane approach to decrease memory usage by having different tree roots sharing the same leaves. This reduces the total number of nodes from 742900*13 to 1440025 for A=13.

The nodes can be built easily using DP (the code has less than 50 lines).

And miraculously this solution passed the checker.