Evaluating tree data iteratively Community,

I'm working on a project lifting assembler code to a AbstractSyntaxTree-like structures like these:



In order to be able to evaluate the final value of a tree given only leafes with constant values, I implemented an recursive approach: Each node class has its own value function. For all nodes except constants, it will query the value function of its children.

e.g. A add node has a value function which works like this:

self.children[0].value() + self.children[1].value()


This seems simple and stores Operation-Logic where it belongs: into operation nodes. The main problem is that these trees tend to be become very large and I fear an recursive approach might not be the best way here.

The most common operations ran on this tree are tree merging and optimization (transversal + modification). At the moment we use single-linked notes, since this serves the use cases in the best way.

Is there any iterative way of archiving this value evaluation? Any help appreciated.
A recursive function is only bad if it ends up repeating work and in this case it does not have too. A postorder traversal of the tree is what you want to do here, and the iterative solution exists, but is considerably more difficult to implemant. A post order traversal will only visit each node once, and you will not beat that for complexity.