 # What is the Memory Limit?

#1

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?

#2

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.

#3

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.

#4

problem stupid, memory limits way too strict.

#5

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.

#6

@amir-r

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)
continue;
// 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)
output.push_back(nodes[i]);
else if (i < parent[i])
nodes[parent[i]]->left = nodes[i];
else
nodes[parent[i]]->right = nodes[i];
}
}

int num_output = 0;

void generate(int to_process) {
if (to_process == store.size()) {
doOutput();
return;
}

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);
return;
}

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);
store.pop_back();
store.pop_back();
}
}

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

generate(0);
store.clear();

return std::move(output);
}
``````

#7

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.