I am iterating over a tree through an API. This API provides a list of nodes sorted in post order DFS. I need to gather data for each node in the tree, combine that data with the parent's data (according to some heuristic not just a simple arithmetic accumulation). Another way to look at this, is that each node in the tree gathers data about its children and combines it to make its own data. Its parent, in turn, will use this data and combine it with its children.There is no way to annotate the tree with the intermediate data. (No write permissions) Somehow, I need to associate each node of the tree with some data. One approach would be to use a map of some sort. The issue is that these N nodes do not have ids from 0 to N, so the map could introduce a O(Nlog(N)) complexity in an algorithm that should just be O(N).Intuitively and by running a few examples, I can up with the pseudo code below.StackOfData stack for each node in post ordered list  data=initialize()     # Sibling order does not matter,   # all we care is popping the stack once for each child     for each child of node    childData = stack.pop()    data = combine(data,childData)     end  mydata = node.extractData()     data = combine(data, mydata)     stack.push(data)endI am not so much looking for alternate ways of solving this problem. I am solely trying here to fill an academic void.My question is :Is there some theoretical proof to substantiate the above pseudo-code? Thanks for the help.
Collecting and combining data from iterative DFS on read-only trees
algorithms;trees;stacks