Does map of stacks require n square space?

Question

I was working on this geeksforgeeks question:

Check Mirror in N-ary tree

Given two n-ary trees. Check if they are mirror images of each other or not. You are also given e denoting the number of edges in both trees, and two arrays, A[] and B[]. Each array has 2*e space separated values u,v denoting an edge from u to v for the both trees.

So the given parameters are two arrays representing edges between the nodes of two trees (arr1[0] has an edge with arr1[1] and arr1[2] has and edge with arr1[3] and so on).

I did it using two 2-D vectors by just pushing the edges for both trees on their nodes and then reversing all edges of one tree and finally checking if now all edges of both trees are same .

It was a correct answer, but the optimal solution required should be using O(n) space, which I clearly violated using a 2-D array. (n=number of nodes)

Their solution uses a map defined as map<int,stack<int>> m and then similar kind of approach what I used.

My question is, is it really a O(n) space solution? Doesn't a map of stacks require n² space as every index will be using a stack of O(n) size?

Also, any hints regarding any other optimal solution (with respect to space, timely optimal solutions I wish to find on my own) will be grateful.

Answer 1

First of all there is some ambiguity in the definition of 𝑛: there is mention of 𝑛-ary trees and of 𝑛 nodes. Let's speak of 𝑘-ary trees instead, to avoid confusion. But honestly, I think the original question (on GfG) should not have spoken of "𝑛-ary trees" (which tells something about the branching factor, see Wikipedia), but of "trees with 𝑛 nodes".

Does map of stacks do not require n squared space as every index will be using a stack of O(n) size ?

No, even though one stack could have O(𝑛) size, one such large stack restricts the sizes of the other stacks. A tree has O(𝑛) edges -- actually, exactly 𝑛−1 edges -- so the sum of the sizes of the stacks is still O(𝑛), and so the total memory usage is O(𝑛) for the key/reference pairs in the map, and O(𝑛) for the stacks, which amounts to O(𝑛).