Facing Memory Limit exceeded. How many nodes can I create within the problem limits

#1

How many nodes can I create in total. Below is the number of nodes created by my program for different values of N:
N: 1 Trees: 1 Nodes: 1
N: 2 Trees: 2 Nodes: 4
N: 3 Trees: 5 Nodes: 14
N: 4 Trees: 14 Nodes: 49
N: 5 Trees: 42 Nodes: 175
N: 6 Trees: 132 Nodes: 637
N: 7 Trees: 429 Nodes: 2353
N: 8 Trees: 1430 Nodes: 8788
N: 9 Trees: 4862 Nodes: 33098
N: 10 Trees: 16796 Nodes: 125476
N: 11 Trees: 58786 Nodes: 478192
N: 12 Trees: 208012 Nodes: 1830270
N: 13 Trees: 742900 Nodes: 7030570
N: 14 Trees: 2674440 Nodes: 27088870
N: 15 Trees: 9694845 Nodes: 104647630

Can anyone let me know if this looks correct?
PS: I’ve counted number of nodes by placing a counter inside constructor of “TreeNode”, like this:

TreeNode(int x) : val(x), left(nullptr), right(nullptr) {
    nodeCount++;
}
#2

Late reply if you haven’t figured it out :slight_smile:
some nodes are actually the same:
with A=3 as in the exemple, I count 15 nodes (5 roots = level 0, 6 level 1 (2 leafs, 4 intermediate nodes) and 4 level 2 (leafs)). Idon’t know how you got 14 but that is probably unimportant.
What is important : leaf nodes with identical values could actually be the same nodes, that reduces by 3 our nodes. And for higher value of A, even some intermediate nodes can be shared by several tree.
for exemple :
(1<2>3) is the same in ((1<2>3)<4)<5 and in (1<2>3)<4>5
that’s a good memory save for higher values of A (I am too lazy to do the calculations, sorry)

#3

I saw the Memory Limit exceeded error because I didn’t to a recursive delete on a duplicate tree allocated with new. If you use malloc() to allocate nodes, you would need to do a recursive free();